М-Чм-зао-09
.pdfПермский государственный технический университет Строительный факультет
Кафедра строительной механики и вычислительной техники
Методические указания для самостоятельной работы и контрольные задания по дисциплине
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
для студентов заочников специальностей ПГС-290300, ВВ-290800
ПСК-290600, ТВ-290700
Пермь 2009
План УМД 2009\2010 уч.г.
Методические указания для самостоятельной работы и контрольные задания по дисциплине
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
Составитель: Кашеварова Г.Г., к.т.н., доцент, Пермякова Т.Б., к.т.н., доцент.
Приведены методические указания по самостоятельному изучению дисциплины "Численные методы решения задач", задания и методические указания по выполнению контрольных работ. Предназначены для студентов заочного факультета.
Рецензент: С.Г.Кузнецова к.т.н., доцент
Издание стереотипное.
Утверждено на заседании кафедры СМиВТ от 8 октября 2009 г.
2
Введение
Студенты, обучающиеся на строительном факультете специальности ПГС-290300, ВВ-290800 ПСК-290600, ТВ-290700 заочного отделения изучают дисциплину "Численные методы решения задач ".
Распределение объемов занятий и видов учебной работы дано в табл.1.
Таблица 1.
Семе |
|
Занятия, ч. |
|
Контроль |
|
стр |
Лекции |
Практиче |
Самостоятель |
|
|
|
|
ские |
|
ная работа |
|
5 |
6 |
6 |
|
118 |
Зачет |
Основной формой изучения дисциплины является самостоятельная работа студента над рекомендованной литературой. Целесообразно прорабатывать материал, пользуясь приведенным ниже списком вопросов и краткими пояснениями к ним.
Список литературы Основная
1.Кашеварова Г.Г., Пермякова Т.Б. Численные методы решения задач строительства на ЭВМ. Пермь. 2003.-351с.
2.Турчак Л.И. Основы численных методов. М.: Наука 1987.-342с.
3.Волков Е.А. Численные методы. -М. Наука. 1987. –248 с.
Литература дополнительная
4.А.А.Самарский, А.В.Гулин. исленные методы. М. Наука. 1989. -430с.
5.Б.П.Демидович, И.А.Марон. Численные методы анализа. М. "Наука". 1967.-368с.
6.С.И. Зуховицкий. Линейное и выпуклое программирование. . М. "Наука". 1964.-348с.
7.Попов А. Excel. Практическое руководство. М.: ДЕСС КОМ. 2000. -354
с.????????
Краткие методические указания по самостоятельному изучению курса
Методические указания содержат формулировку вопроса, номер
соответствующего раздела в рекомендованной литературе и сжатый комментарий.
1.Численные методы решения задач линейной алгебры [1, глава 1].
ØПрямые (точные) методы решения систем линейных алгебраических уравнений. Метод Гаусса.
ØВычисление определителя и обратной матрицы методом Гаусса.
ØОбусловленность матриц. Плохо обусловленные системы линейных алгебраических уравнений.
ØИтерационные методы решения систем линейных алгебраических уравнений. Метод Якоби и Гаусса-Зейделя. Условия сходимости итерационного процесса.
ØСпециальные типы матриц, возникающие в практических задачах.
3
2.Численные методы решения обыкновенных дифференциальных уравнений [1, глава 6, п.п.6.1, 6.4, .6.6].
ØЗадачи Коши и краевые задачи в расчетах строительных конструкций. Необходимость решения их численными методами.
ØРазностная схема решения краевой задачи для линейного дифференциального уравнения 2-го порядка.
3.Численные методы оптимизации [1, глава 8, п.п.8.1, 8.3,8.5].
ØМатематические задачи оптимизации в строительстве.
ØЗадача линейного программирования. Геометрическая интерпретация задачи линейного программирования. Симплекс-метод решения задач линейного программирования.
Задания на контрольные работы и методические указания к их выполнению
Контрольную работу каждый студент выполняет в соответствии с индивидуальным вариантом. Номер варианта определяет преподаватель. Варианты заданий приведены в приложениях.
Работа выполняется с использованием электронных таблиц Microsoft Excel. Рабочие лист Excel должны содержать все расчеты, необходимые для решения поставленной задачи и соответствующие выводы. Выводы можно сделать вручную непосредственно на распечатке рабочего листа. Распечатка должна содержать: фамилию, имя, код группы, краткую постановку задачи, номер варианта.
Контрольные работы должны быть представлены на бумажном (распечатка) и электронном (дискета) носителях.
Работы, выполненные полностью или частично, не по заданному варианту не рецензируются.
Защита контрольных работ происходит по расписанию в дисплейном классе с обязательной демонстрацией проведенных расчетов в Excel. Для успешной защиты необходимо:
Øуметь объяснить ход выполнения расчетов, правильность использования расчетных формул и графических построений, понимать смысл входящих в них величин;
Øуметь объяснить полученные результаты;
Øзнать идеи используемых численных методов в пределах программы курса.
4
Контрольная работа №1
Тема. Численные методы решения задач линейной алгебры,
метод Гаусса
За д а н и е
1.Решить систему линейных алгебраических уравнений (СЛАУ) AX =B,
вычислить определитель и обратную матрицу для матрицы А методом исключения Гаусса.
2.Сделать выводы о корректности задачи (существование, единственность, устойчивость решения относительно исходных данных).
Указания к выполнению первой работы Порядок выполнения работы
1.Для расчета использовать матрицу А, заданную в соответствии с вариантом из приложения 1. Вектор свободных членов B задать произвольно.
2.Решить полученную вами СЛАУ AX =B методом Гаусса:
Øпрямой ход: привести СЛАУ к эквивалентной системе с
треугольной матрицей системы, т.е. A X = B
Øобратный ход: последовательно вычислить неизвестные х1,х2,…,хn
3.Проверить полученное решение СЛАУ, используя надстройку Excel
поиск решения применительно к исходной системе AX = B .
4.Вычислить вручную методом Гаусса определитель матрицы А, матрицу А-1, обратную матрице A,. Проверить сделанные расчеты на ЭВМ, используя матричные функции Excel.
5.Вычислить нормы матриц А и А-1 (вручную).
6.Исследовать обусловленность матрицы, вычислив меру
обусловленности ν(А). Сделать заключение об обусловленности матрицы A и заданной системы.
7.Задать небольшое возмущение исходных данных (~0.1) и снова решить систему, используя надстройку поиск решения. Проанализировать, как изменились результаты, оценив относительную погрешность решения (%).
8.Проанализировав полученные данные, сделать заключение о корректности исходной задачи.
1.1. Теоретические сведения
1.Система линейных алгебраических уравнений в общем случае имеет
вид:
a11x1 + a12 x2 +......... |
+a1n x n = b1 |
|
|
a21x1 + a22 x2 +......... |
+a2n x n = b2 |
, |
(1.1) |
.......................................... |
|
|
|
an1x1 + an2 x2 +......... |
+ann x n = bn |
|
|
|
5 |
|
|
В некоторых случаях эту систему удобнее записывать в матричной
форме:
_ _ |
(1.2) |
A ´ X = B , |
|
_ |
_ |
где А - матрица системы, X - вектор решения, B - вектор свободных членов.
|
éa |
|
a |
|
K a |
1n |
ù |
|
éx |
ù |
|
éb |
ù |
|
ê |
11 |
|
12 |
|
ú |
|
ê 1 |
ú |
|
ê 1 |
ú |
|
A = |
êa21 |
a22 |
K a2n ú |
_ |
êx2 ú |
_ |
êb2 ú |
||||||
êK K K K ú |
; X = |
êKú |
; B = |
|
. |
||||||||
|
|
|
êKú |
||||||||||
|
ê |
|
an2 |
|
|
ú |
|
ê |
ú |
|
ê |
ú |
|
|
ëan1 |
K ann û |
|
ëxn |
û |
|
ëbn |
û |
2.Система (1.1−1.2) имеет единственное решение, если матрица А является невырожденной (detA¹0).
3.Матрицы А и В являются исходными данными и во многих случаях задаются приближенно. Встает вопрос, как погрешности исходных данных влияют на точность решения.
Говорят, задача плохо обусловлена, если она чувствительна к малым изменениям входящих в нее исходных данных. В противном случае – хорошо обусловлена.
Обусловленность является качественной характеристикой, хотя мы будем стараться оценить ее и количественно, используя величину меры
обусловленности
ν ( A) = |
|
|
|
A |
|
|
|
* |
A−1 |
. |
(1.3) |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
4.Матрица А-1 называется обратной по отношению к данной матрице А
инаходится из условия
А А-1= А-1 А =Е. |
(1.4) |
Процесс нахождения обратной матрицы называется обращением матрицы. Доказывается теорема, что если определитель матрицы А отличен от нуля ( det A ¹ 0), то она имеет обратную матрицу А-1.
5. Величина А называется нормой матрицы A = [aij ]и определяется по одной из 3-х формул:
|
A |
|
|
|
1 |
= max å|aij |
|; |
|
|||
|
|
|
|
||||||||
|
|
|
|
|
|
|
i |
j |
|
|
|
|
A |
|
|
|
1 |
= max å|aij |
|; |
(1.5) |
|||
|
|
|
|||||||||
|
|
|
|
|
|
|
j |
i |
|
|
|
|
A |
|
|
|
3 |
= |
å|aij |
|2 . |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
i , j |
|
|
|
|
6.Система (1.1-1.2) является хорошо обусловленной, а ее решение – |
|||||||||||
устойчивым, если мера обусловленности ν ( A) |
близка единице. |
7. Задача решения СЛАУ является корректной, если решение существует и единственно (detA¹0) и устойчиво относительно исходных данных (А и В), т.е. малым изменениям исходных данных соответствуют малые изменения решения задачи.
6
8. Метод Гаусса (метод последовательного исключения). Суть метода
заключается в последовательном исключении неизвестных из системы уравнений. Процесс состоит из двух этапов: прямого и обратного ходов. В результате прямого хода система приводится к треугольному виду, а при выполнении обратного хода вычисляются все неизвестные.
Продемонстрируем метод Гаусса на примере системы из трех уравнений. Обозначим каждое уравнение буквами A(i) , B(i), C(i) (здесь (i) соответствует номеру шага).
a |
x + a |
x |
+ a |
x |
= b ; |
A(0) |
|
|
11 |
1 |
12 |
2 |
13 |
3 |
1 |
|
(1.6) |
a21x1 |
+ a22 x2 + a23x3 |
= b2 ; |
B(0) |
|||||
a |
x |
+ a |
x |
+ a |
x |
= b ; |
C(0) |
|
31 |
1 |
32 |
2 |
33 |
3 |
3 |
|
|
Прямой ход.
Шаг 1. Допустим, a11 отличен от нуля (ведущий элемент). Разделим 1-ое уравнение на a11 . Умножим последовательно коэффициенты полученного уравнения на (- a21 ) и (- a31 ) и суммируем с соответствующими элементами - 2- ой и 3-ей строк. Выполняемые действия показаны справа от системы уравнений. В результате выполнени этого шага из всех уравнений, кроме 1-го исключено неизвестное х1.
x + a(1) x |
+ a(1) x |
= b(1) |
; |
|
A(1) |
= A(0) / a |
|
|
|||
|
|
|
|||||||||
1 |
12 |
2 |
13 |
3 |
1 |
|
|
|
11 |
|
|
|
a(1) x + a(1) x |
3 |
= b(1) |
; |
|
B(1) |
= B(0) + A(1) * (−a |
21 |
) |
||
|
22 |
2 |
23 |
2 |
|
|
|
|
|
||
|
a(1) x + a(1) x |
3 |
= b(1) |
; |
|
C(1) |
= C(0) + A(1) (−a |
) |
|||
|
32 |
2 |
33 |
3 |
|
|
|
|
31 |
|
Шаг 2. Первое уравнение остается неизменным. Исключим неизвестное х2 из 2-го и 3-го уравнений. Выполняемые действия показаны справа от системы уравнений.
x + a(1) x |
+ a(1) x |
= b(1) ; |
|
A(2) = A(1) |
|
||||
1 |
12 |
2 |
13 |
3 |
1 |
|
|
|
|
|
|
x2 |
+ a23(2) x3 |
= b2(2) ; |
B(2) |
= B(1) / a22(1) |
(1.7) |
||
|
|
|
a(2) x |
= b(2) |
; |
C(2) |
= C(1) + B(2) (−a |
(1) ) |
|
|
|
|
33 |
3 |
3 |
|
|
32 |
Выполнив 2 шага для системы 3-го порядка, получили систему (1.7), эквивалентную заданной. Матрица этой системы является треугольной и неизвестные системы вычисляются достаточно легко.
Обратный ход. Из последней строки полученной системы (1.7) находим
b(2)
значение 3-ей компоненты вектора-решения x3 = a3(2) . Подставляя его во вторую
33
строку системы, получим вторую компоненту вектора-решения x2 = b2(2) − a23(2) x3 . Имея x2 , x3 , аналогичным образом найдем x1 из первого уравнения системы (1.7)
x1 = b1(1) − a12(1) x2 − a13(1) x3 .
7
1.2. Решение задач линейной алгебры с использованием приложения
Microsoft Excel
1.2.1. Матричные функции Excel
Для решения задач линейной алгебры используются матричные функции Excel из категории математические:
МУМНОЖ(<матрица1>;<матрица2>) – возвращает произведение
матриц.
МОБР(<матрица>) – возвращает матрицу, обратную к данной. МОПРЕД(<матрица>) – вычисляет определитель исходной
квадратной матрицы.
Порядок обращения к матричным функциям:
Øвыделить блок, где будет размещен результат матричной операции;
Øв мастере функций выбрать нужную категорию и нужную функцию;
Øубрать окно соответствующей функции (с помощью кнопки ) или отбуксировать его в сторону от исходных данных;
Øвыделить исходную матрицу (бегущая пунктирная линия);
Øодновременно нажать клавиши Shift+Ctrl+Enter.
1.2.2. Реализация метода Гаусса средствами приложения Excel
Пример 1.1. Найти решение системы линейных алгебраических
уравнений
2x1 |
+ 4x2 + 3x3 = 4 ü |
|
3x1 |
+ x2 - 2x3 = -2 ýï , |
(1.8) |
4x1 |
ï |
|
+ 11x2 + 7x3 = 7þ |
|
используя алгоритм метода Гаусса.
Последовательность действий:
Возьмем чистый лист Excel, назовем его Гаусс. Введем расширенную матрицу системы, как показано на рис.1.1 в ячейки А3:D5.
Первый этап, приведение матрицы системы к треугольной.
1.Поделим элементы первой строки на а11 .Для этого в ячейку А7 введем формулу А7=А3/A$3$ (*смотри сноску) и скопируем ее вправо до конца строки.
2.Умножим элементы первой строки на (-а21 ) и прибавим ко 2-ой строке. Для этого введем формулу А8=А7(-А$4$)+А4 и скопируем ее вправо до конца строки.
3.Умножим элементы первой строки на (-а31 ) и прибавим к 3-ей строке. Для этого введем формулу А9=А7(-А$5$)+А5 и скопируем ее вправо до
конца строки. Таким образом исключили неизвестное х1 из 2-го и 3-го уравнений системы (смотри 1-ый шаг рис.1.1).
*- данная запись означает, что в ячейку А7 вводится формула, начинающаяся со знака «=» (равно).
8
4. Осталось исключить неизвестное х2 из 3-го уравнения системы. Для этого реализуем описанный выше алгоритм для 2-ой и3-ей строк (смотри
2-ой шаг рис.1.1).
Рис.1.1.
На этом первый этап метода Гаусса, закончен, матрица системы приведена к треугольной.
Второй этап. Здесь последовательно найдем неизвестные, начиная с последней строки. Для этого в ячейки G12:G14 запишем формулы:
G4=D13/C13 |
(для вычисления x3); |
|
|
|
|
|||||||||
G3=D12-C12*G4 |
(для вычисления x2); |
|
|
|
|
|||||||||
G2=D11-C11*G4-B11*G3 |
(для вычисления x1). |
|
|
|
|
|||||||||
1.2.3. Решение СЛАУ с помощью надстройки |
|
|
|
|
||||||||||
|
|
|
|
Поиск решения |
|
|
|
|
||||||
Пример 1.2: Найти решение СЛАУ из примера 1.1, используя надстройку |
||||||||||||||
Поиск решения. |
|
|
|
|
|
|
|
|
использует итерационные |
|||||
При решении СЛАУ AX |
=B приложение Excel |
|||||||||||||
(приближенные) методы. Строится последовательность приближений |
|
|
(i ) , |
|||||||||||
X |
||||||||||||||
i=0,1,…n. Назовем вектором невязок следующий вектор: |
|
|
|
|
||||||||||
|
|
R ( i ) = A |
|
( i ) − |
|
|
|
|
|
|
||||
|
|
X |
B |
(1.9) |
|
(i) , |
||||||||
Задача Excel заключается в том, |
чтобы найти такое приближение |
|
|
|||||||||||
|
X |
при котором вектор невязок был бы нулевым, т.е. добиться совпадения значений правых и левых частей системы AX=B.
9
Последовательность действий
1. Возьмем новый лист (а можно и на том же). Заготовим таблицу, как показано на рис.1.2.
Рис.1.2.
2. Заготовим ячейки А7:С7, где будет сформировано решение системы (х1, х2, х3). Первоначально они остаются пустыми, т.е. равными нулю. Однако для контроля правильности вводимых далее формул, удобно ввести в эти ячейки какие-либо значения, например единицы. Эти значения можно рассматривать
как нулевое приближение решения системы, X ( 0 ) (1, 1 , 1) .
3.Введем коэффициенты системы (матрицу А) в ячейки А3:С5.
4.В столбец D введем выражения для вычисления левых частей исходной системы. Для этого в ячейке D3 введем и скопируем вниз до конца таблицы формулу: D3=СУММПРОИЗВ (A3:C3;$A$7:$C$7).
Используемая функция СУММПРОИЗВ принадлежит категории
Математические.
5.В столбец Е запишем значения правых частей системы (матрицу B).
6.В столбец F введем невязки в соответствии с формулой (1.9), т.е. введем формулу F3=D3-E3 и скопируем ее вниз до конца таблицы.
7. Будет не лишним проверить правильность вычислений для случая
X ( 0 ) (1, 1 , 1) .
8. Зададим команду меню Сервис\Поиск решения. В окне Поиск решения (рис.1.3) в поле
Изменяя ячейки укажем блок $А$7:$С$7, а в поле
Ограничения – $F$3:$F$5=0.
Для этого надо щелкнуть на кнопке Добавить и ввести эти ограничения.
9. Щелкнем на кнопке
Выполнить.
Рис. 1.3.
Полученное решение системы (1.8) х1=1; х2=-1 х3=2 записано в ячейках А7:С7, рис.1.2.
10