Численные методы. Ионкин (2012) (неоффициальные) (косяки есть) (1160437)
Текст из файла
Московский государственный университет имени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиНеофициальные конспекты лекций численных методов 3-гокурса 3-го потока (версия 8.0)лектор Н.И. ИонкинМосква2012Данные конспекты отражают содержание лекционного курса «Численные методы», читаемого студентам факультета вычислительной математики и кибернетикиМГУ им. М. В. Ломоносова. Конспекты составили студенты 3–го курса кафедры СПА.С. Колганов, И.Т. Ядгаров, О.В. Горемыкин и Д.М. Биренбаум.
Конспекты неявляются официальной литературой и не могут быть использованы в качестве основного материала на экзамене. За все ошибки, допущенные в данных конспектах,составители ответственности не несут.Отдельная благодарность за исправление ошибок: Байбородову А., ФедоровуА.,Белышову М.,Каганову В.,Моисееву Б.,Бабакову А., Пушину К.c Факультет вычислительной математики и кибернетикиМГУ им. М. В. Ломоносова, 2012 г.Оглавление1 Численные методы линейной алгебры§1 Введение . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§2 Связь метода Гаусса с разложением матрицы на множители . . . . . . . .§3 Обращение матриц методом Гаусса-Жордана . . . . . . . . . . . . . . . .§4 Метод квадратного корня . . . . . . . . . . . . . . . . . . . . . . . . . . . .§5 Примеры и канонический вид итерационных методов решения СЛАУ .
.§6 Теоремы о сходимости итерационных методов . . . . . . . . . . . . . . . .§7 Оценка скорости сходимости итерационных методов . . . . . . . . . . . .§8 Исследование сходимости попеременно треугольного итерационного метода§9 Методы решения задач на собственные значения . . . . . .
. . . . . . . .§10 Приведение матрицы к верхней почти треугольной форме . . . . . . . .§11 Понятие QR – алгоритма. Решение полной проблемы собственных значений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§12 Предварительное преобразование матрицы к верхней почти треугольнойформе . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 Интерполирование и приближение функций§1 Постановка задачи интерполирования . . . . . . . . . . . . . . . . . . . .§2 Интерполяционная форма Лагранжа Ln (x) . . . . . . . . . . . . . . . . .§3 Разделенные разности . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .§4 Интерполяционная формула Ньютона . . . . . . . . . . . . . . . . . . . .§5 Интерполирование с кратными узлами. Полином Эрмита . . . . . . . .§6 Использование полинома H3 (x) для оценки погрешности квадратурнойформулы Симпсона . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .§7 Наилучшее среднеквадратичное приближение функций . . . . . . . . .3 Численное решение нелинейных уравнений и системуравнений§1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§2 Метод простой итерации . . . . . . . . . . . . . .
. . . . . .§3 Метод Ньютона и метод секущих . . . . . . . . . . . . . . .§4 Сходимость метода Ньютона. Оценка скорости сходимости4548505051525455. 58. 61нелинейных............4 Разностные методы решения задач математической физики2.....445811141826293340....................656566687173Оглавление3§1 Явная разностная схема для первой краевой задачи уравнения теплопроводности . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .§2 Чисто неявная разностная схема (схема с опережением) для первой краевой задачи уравнения теплопроводности . . . . . . . . . . . . . . . . .§3 Симметричная разностная схема (схема Кранка–Никольсона) для первойкраевой задачи уравнения теплопроводности . . . . . .
. . . . . . . . .§4 Задача Штурма-Лиувилля . . . . . . . . . . . . . . . . . . . . . . . . . . .§5 Разностная схема с весами. Погрешность аппроксимации на решение . .§6 Разностные схемы для уравнения Пуассона (задача Дирихле) . . . . . . .§7 Разрешимость разностной задачи Дирихле. Сходимость разностной схемы§8 Методы решения разностных схем для задачи Дирихле . . . . .
. . . . .§9 Основные понятия теории разностных схем: аппроксимация, устойчивость, сходимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 Методы решения обыкновенных дифференциальных уравненийсистем ОДУ§1 Постановка задачи Коши и примеры численных методов интегрированиязадачи Коши .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§2 Методы Рунге-Кутта . . . . . . . . . . . . . . . . . . . . . . . . . . . . .§3 Многошаговые разностные методы решения задачи Коши . . . . . . . .§4 Понятие устойчивости многошаговых разностных методов .
. . . . . . .§5 Жесткие системы ОДУ . . . . . . . . . . . . . . . . . . . . . . . . . . . .§6 Дальнейшее определение устойчивости и примеры разностных схем, интегрирования жестких систем дифференциальных уравнений . . . . .737880828688909394и97.....97100104106110. 113Глава 1Численные методы линейной алгебры§1 ВведениеРассмотрим матричное уравнение видаAx = f,(1)где A — матрица размера (m × m), |A| =6 0,x = (x1 , x2 , . . . , xm )T,f = (f1 , f2 , .
. . , fm )T.Так как матрица A невырождена, то решение системы (1) существует и единственно. Существует две группы методов поиска решения системы линейных алгебраических уравнений:1. Прямые методы.2. Итерационные (приближенные) методы.Также будем рассматривать задачу на собственные значения:Ax = λx,(2)где x 6= 0 — собственные векторы, λ — собственные значения.
При численном решении задачи на собственные значения обычно рассматривают две проблемы:1. Частичная проблема собственных значений.2. Полная проблема собственных значений – QR алгоритм.В этой главе также будет решена задача нахождения обратной матрицы.45§2 Связь метода Гаусса с разложением матрицы намножителиРассмотрим матричное уравнение видаAx = f,(1)где A — матрица размера (m × m), |A| =6 0.C помощью элементарных преобразований в прямом ходе метода Гаусса получаем верхнетреугольную матрицу с диагональными элементами, равными 1:1 a12 .
. . a1m0 1 . . . a2m .. ...... . ... 0 0 ...1m3 − mдействий (умножений иСведение матрицы A к данному виду требует3m(m + 1)делений). Кроме того требуется— для преобразования правой части, а для2m(m − 1)обратного хода метода Гаусса потребуетсядействий.2Представление матрицы A в видеA = BC(2)называется факторизацией матрицы A. Матрицы Bb11 0 . . .01 b21 b22 . . .0 0B = ........ C = ... .... bm1 bm2 . .
. bmm0и C имеют вид:c12 . . . c1m1 . . . c2m ...... ... 0 ... 1Покажем, что нахождение элементов матриц B и C возможно при определенномограничении на матрицу A. Запишем представление (2) поэлементно:aij =mXbil clj .l=1Представим эту сумму в виде:aij =i−1Xbil clj + bii cij +l=1mXl=i+1Так как bil = 0, l > i, l = 1, m то:bii cij +i−1Xl=1bil clj = aijbil clj .6Поделим обе части на bii и выразим cij (для этого требуется bii 6= 0):aij −cij =i−1Pbil cljl=1, i<jbii(3)Перепишем разложение матрицы A = BC в виде :aij =j−1Xbil clj + bjj cjj +l=1Учитывая, чтоmPmXbil clj .l=j+1bil clj = 0 в силу того, что clj = 0,j < l и cjj = 1, получим:l=i+1bij = aij −j−1Xbil clji>j(4)l=1Алгоритм нахождения матриц B и C в представлении (2):1.
b11 = a11 , c1j =a1jb11=a1j,ja11= 2, m, то есть нашли все элементы c1j .2. bi1 = ai1 ⇒ нашли все элементы bi1 .3. Исходя из первых двух пунктов найдем диагональный элемент b22 .4. И так далее.Утверждение. Пусть все главные угловые миноры матрицы A отличны от нуля.Тогда факторизация матрицы A, представленная в виде (2), возможна единственным образом.Доказательство: Введем ∆0 = 1.
В силу того, что Ai = Bi Ci ⇒ |Ai | = |Bi ||Ci |. Таккак главная диагональ матрицы C состоит из единиц, то |Ai | = ∆i = b11 b22 . . . bii ⇒i, i = 1, m ⇒ bii 6= 0.bii = ∆∆i−1Связь метода Гаусса с разложением матрицы A на множителиРассматриваем систему (1) порядка m и факторизацию матрицы A (2):(BY = f(5)BCx = f ⇒Cx = Y(6)Задача. Доказать, что нахождение матриц B и C требуетделений.m3 −m3умножений и7Решение: Воспользуемся формулами для факторизации матрицы:bij = aij +j−1Xbil clj , i > jl=1Для вычисления каждого bij потребуется j − 1 умножение. Тогда зафиксировав индекс i, получим:iXi(i − 1)(j − 1) =2j=1Далее посчитаем для индекса i:mXi(i − 1)i=12mm1X 2 1X=i −i2 i=12 i=1Нетрудно получить значение первой суммы:щая будет равна:m(m + 1)(2m + 1).
Тогда результирую6m(m + 1)(2m + 1) m(m + 1)m(m + 1)(m − 1)−=1246Далее для вычисления элементов cij воспользуемся формулойaij −cij =i−1Pl=1biibil clj, i<jДля каждого cij потребуется i − 1 умножений и одно деление. Зафиксируем индексj:j−1Xj(j − 1)j=2i=1И для индекса j получаем аналогичную формулу:mXj(j − 1)j=12mmm(m + 1)(2m + 1) m(m + 1)1X 2 1Xm(m + 1)(m − 1)j −j==−=2 j=12 j=11246Просуммируем два полученных результата для окончательно ответа:m(m + 1)(m − 1) m(m + 1)(m − 1)m3 − m+=663В прямом методе Гаусса при сведении матрицы к верхнетреугольному виду с едиm3 − mницами на главной диагонали требуетсядействий, то есть в точности такое3число, что и для факторизации матрицы A.8Распишем покоординатно системы (5) и (6):bi1 y1 + bi2 y2 + · · · + bii yi = fi , i = 1, mxi + cii+1 xi+1 + · · · + cim xm = yi , i = 1, mСчитая, что bii 6= 0, выразим yi и xi :fi −i−1Pbil yll=1yi =(5∗)biixi = yi −mXcil xl(6∗)l=i+1m(m + 1) m(m − 1)+действий.
Для преобразования22m(m + 1)правых частей в методе Гаусса требуется, что совпадает с числом действий2m(m − 1)в системе (5*). Для обратного хода метода Гаусса требуетсядействий, что2совпадает с числом действий в системе (6*). Тогда общее количество действия дляметода Гаусса равно:m3 − m+ m2 .3Эти две формулы требуют§3 Обращение матриц методом Гаусса-ЖорданаРассмотрим матричное уравнение видаAx = f,(1)где A — матрица размера (m × m), |A| =6 0Так как определитель матрицы A не равен нулю, то существует обратная к нейматрица и, по определениюA−1 A = AA−1 = EОбозначим A−1 = X, тогда получим уравнениеAX = E,где X = xij , i, j = 1, m.Для решения системыAX = Eметодом Гаусса требуется число операций порядка m6 .
Покажем, что число действийможно снизить до m3 .9Распишем покоординатно:mXail xlj = δij– в этой системе m2 неизвестныхl=1Введем вектор-столбецx(j) = (x1j , x2j , . . . , xmj )T ,i = 1, m.Введем вектор правых частей единичной матрицы и обозначим егоδ (j) = (0, 0, . . . , 0, 1, 0, . . . , 0, 0),где на j позиции стоит единица.Тогда видно, что для того чтобы обратить матрицу, необходимо решить m системAx(j) = δ (j) ,j = 1, m(2)Таким образом, решение системы с m2 неизвестными сведено к решению m систем с m неизвестными и фиксированной матрицей A. Теперь применим факторизацию (предполагая, что необходимое условие выполнено, т.е.
все угловые минорыотличны от нуля): A = BC.Вновь расписав уравнение, получимBCx(j) = δ (j) .Обозначая вектор Cx(j) = Y (j) , видим, что для решения системы (2) нужнорешить две системы:(3)BY (j) = δ (j) , j = 1, mCx(j) = Y (j) ,j = 1, m(4)Эти системы имеют треугольные матрицы, поэтому все неизвестные находятсяпо явным формулам. Следовательно,по совокупности эти две системы требуют m2действий.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
