Численные методы. Ионкин (миниметодичка) (2015) (1160460), страница 2
Текст из файла (страница 2)
. . , ).Пусть положительная симметричная матрица ( = * > 0) являетсяматрицей со строгим диагональным преобладанием:Следствие 2. >∑︁| |, = 1, .=1,̸=Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении 0 .Задача.Пусть матрица = * > 0. Доказать, что > 0, = 1, .Пусть = * > 0.
Тогда метод Зейделя сходится в среднеквадратичнойнорме при любом начальном приближении 0 .Следствие 3.Следствие 4.Пусть = * > 0, 2 = max > 0. Если 0 < <16622 ,то метод простойитерации сходится в среднеквадратичной норме при любом начальном приближении 0 .§7Оценка скорости сходимости итерационных методовДля[︂]︂достижения заданной точности достаточно провести число итераций, равное 0 () =1ln , где [] — целая часть числа .ln 1Определение.Величина ln1называется скоростью сходимости итерационного метода.*√︀ Пусть = > 0.
Введем энергетическую норму, порождаемую оператором : ‖‖ =(, ).В пространстве существует ортонормированный базис { } из собственных векторовоператора .(об оценке скорости сходимости). Пусть = * > 0, = * > 0. Пустьтакже существует число , 0 < < 1, такое, что выполнено операторное неравенство:Теорема 11−1+66.(1)8Тогда для погрешности итерационного метода = справедлива оценка:‖ +1 ‖ 6 ‖ ‖ ,Замечание.+1 −+ = решения системы(2) ∈ Z+ .Оценка (2) справедлива и в энергетической норме ‖·‖ .Пусть , — самосопряженные положительно определенные операторы,и пусть существуют 2 > 1 > 0, для которых выполняется условие 1 6 6 2 .2Тогда, если = 0 = 1 +, то двухслойный итерационный метод решения системы урав2нений сходится, и верна оценкаСледствие 1.(3)‖+1 − ‖ 6 ‖ − ‖ ,где =1−1+ ,=12 .Для мутода простой итерации, пусть — самосопряженный положительно определенный оператор, а 1 и 2 — его минимальное и максимальное собственные2значения: 1 = min166 , 2 = max166 .
Кроме того, пусть = 1 +2 . Тогда вернаСледствие 2.оценка ‖+1 − ‖ 6 ‖ − ‖, где =§81−1+ ,=12 .ПТИМИсследование скорости сходимостиЗапишем каноническую форму попеременно-треугольного итерационного метода (ПТИМ):( + 1 )( + 2 )+1 − + = , > 0, > 0, ∈ Z+ .Обозначим = ( + 1 )( + 2 ).(о сходимости ПТИМ). Пусть — самосопряженный положительно определенный оператор и > 4 . Тогда ПТИМ сходится в среднеквадратичной норме при любомначальном приближении 0 .Теорема 1(о скорости сходимости ПТИМ). Пусть — самосопряженный положительноопределенный оператор и числа > 0, ∆ > 0 таковы, что выполняются неравенстваТеорема 2 > , 2* 2 6Положим =√2 ,Δ =21 +2 ,√1 =2(︁∆.4)︁√√ Δ√,+ Δ(1)√Δ4 .√1− √1+3 ,2 =имеет место оценка ‖+1 − ‖ 6 ‖ − ‖ , где =Тогда ПТИМ сходится и=Δ.ПТИМ сходится на порядок быстрее метода простой итерации, метода Зейделя и ме-тода Якоби.
В практических(︀ −2 )︀ задачах, когда велико, отношение = Δ часто(︀ )︀ являетсявеличиной порядка O . Оценим скорость сходимости(︀ ПТИМ:()=O . Оценим0)︀2скорость сходимости метода простой итерации: 0 () = O .§9. Методы решения задач на собственные значения§99Методы решения задач на собственные значенияСтепенной методРассмотрим частичную проблему собственных значений. Будем искать собственный векторпо формуле+1 = , ∈ Z+ , 0 задано.(1)Пусть { }=1 — собственные значения матрицы , среди которых могут быть повторяющиеся.
Упорядочим их по неубыванию модулей: |1 | 6 |2 | 6 . . . 6 | |.Будем доказывать сходимость степенного метода при выполнении трех условий:A) В вещественном пространстве R существует базис { }, = 1, из собственныхвекторов матрицы .⃒⃒⃒⃒B) ⃒ −1⃒ < 1.C) 0 = 1 1 + 2 2 + . . . + , где ̸= 0.Пусть вещественная матрица (×) такова, что выполнены условияA) – C). Тогда степенной метод для матрицы сходится по направлению к собственномувектору, отвечающему максимальному по модулю собственному значению: −→ .→∞}︁{︁+1()()Кроме того, для последовательности , заданной одной из формул = , =Утверждение.
, )()1, , либо = ( , )((︃(︂)︂ )︃−1.справедлива следующая оценка сходимости к :()− =OЗамечание. Пусть у вещественной матрицы ( × ) существует комплексное собственное значение: = 0 + 1 , 1 ̸= 0. Тогда соответствующий собственный вектор —комплексный: = 0 +1 , 1 ̸= , и начальное приближение 0 вектора в итерационномметоде также должно быть комплексным.Метод обратных итерацийПусть матрица — невырожденная. Рассмотрим следующую форму записи неявного итерационного метода: +1 = , ∈ Z+ , 0 задано.Сформулируем три условия:A) В пространстве R существует базис { } из собственных векторов матрицы .⃒ ⃒⃒ ⃒B) ⃒ 21 ⃒ < 1.C) 0 = 1 1 + 2 2 + .
. . + , 1 ̸= 0.Пусть невырожденная вещественная матрица ( × ) такова, чтовыполнены условия A) – C). Тогда метод обратных итераций сходится по направлению ксобственному вектору, отвечающему минимальному по модулю собственному значению: −→ 1 .Утверждение.→∞Задача.Пусть выполнены условия A) – C) сходимости метода обратных итераций.10Показать, что(︃в случаепроизвольной матрицыследующие оценки:)︃(︃(︂ )︂ справедливы(︂ )︂ )︃ 11=O1 − +1, 1 − ((+1,,) ) = O. Показать, что если матрица —22(︃(︂ )︂ )︃2самосопряженная, то последнюю оценку можно улучшить: 1 − ((+1,,) ) = O12.Метод обратных итераций со сдвигомРассмотрим итерационный метод, задаваемый формулой (−)+1 = , ∈ Z+ , 0 задано,где — такое вещественное число, что матрица ( − ) невырождена.(︃)︃()Само собственное значение находится из выражения: = lim→∞+(),=+11, .§10Приведение матрицы к верхней почти треугольной формеМатрица имеет⎛ верхнюю× × ×⎜× × ×⎜⎜0 × ×⎜ее можно записать в виде = ⎜ 0 0 ×⎜⎜.
. .⎝ .. .. ..Определение.почти... ×... ×... ×... ×.... ..треугольнуюформу (ВПТФ), если⎞××⎟⎟×⎟⎟, где символами × обозначены,×⎟⎟⎟.. ⎠.0 0 0 ... × ×вообще говоря, ненулевые элементы матрицы.Элементарным отражением, соответствующим вещественному векторстолбцу = (1 , 2 , . . .
, ) , называется преобразование, задаваемое матрицейОпределение. =−212⎜ 2 1⎜ = ⎜ .⎝ ..⎛ .‖‖2(1)⎞· · · 1 · · · 2 ⎟⎟.. ⎟ — симметричная (эрмитова) матрица..... ⎠2 1 2 · · · Сформулируем свойства матрицы элементарного отражения:1 222...1. H — симметрическая матрица, = .2. H — ортогональная матрица, −1 = .Пусть задан вещественный вектор-столбец = (1 , 2 , .., ) . Тогдаможновыбрать вектор так, чтобы было выполнено равенство = (−‖‖, 0, 0, .., 0) , ‖‖ =√︀(, ), где H — элементарное отражение, соответствующее вектор-столбцу .Утверждение.Любую вещественную матрицу ( × ) можно привести к верхнейпочти треугольной форме с помощью преобразования подобия с ортогональной матрицейУтверждение.§11.
Понятие о QR-алгоритме решения полной проблемы собственных значений⎛× × × ...⎜× × × . . .⎜⎜0 × × ...⎜: = −1 = ⎜ 0 0 × . . .⎜⎜. . . ...⎝ .. .. ..0 0 0 ...Замечание 1.××××...11⎞××⎟⎟×⎟⎟, где = −1 .×⎟⎟.. ⎟.⎠× ×Преобразование подобия сохраняет спектр матрицы: = , = 1, .Если — симметрическая матрица, то также является симметрической матрицей: = ⇒ = .Замечание 2.Замечание 3. Симметричная матрица, имеющая верхнюю почти треугольную форму,является симметричной трехдиагональной матрицей.§11Понятие о QR-алгоритме решения полной проблемы собственных значенийПроизвольная матрица (×) может быть представлена в виде: =, где — ортогональная матрица, а — матрица, имеющая верхнюю треугольнуюформу (ВТФ).Утверждение.Число операций, необходимых для вычисления QR-разложения матрицы ,зависит от вида матрицы .
Для произвольной матрицы число операций можно оценить величиной порядка 3 , для матрицы с ВПТФ, — порядка 2 , для трехдиагональнойматрицы — порядка .Замечание.Рассмотрим оптимальную версию QR-алгоритма. Приведем матрицу к матрице 0 ,имеющей ВПТФ, и осуществим QR-разложение матрицы 0 : 0 = 0 0 , где 0 — ортогональная, а 0 — верхнетреугольная матрица. Построим матрицу 1 = 0 0 .На следующем шаге осуществим QR-разложение матрицы 1 = 1 1 и построим матрицу 2 = 1 1 .
Аналогичным образом продолжая вычисления, на -м шаге осуществимQR-разложение матрицы = и построим +1 = .Если все собственные значения матрицы вещественны,⎛ то последова-⎞1 × . . . ×⎜ 0 2 . . . × ⎟⎜⎟тельность матриц { } сходится к матрице, имеющей ВТФ: −→ ⎜ ... . ... ⎟ ..→∞ ⎝ .. . ⎠.0 0 .
. . Если же матрица имеет комплексную пару собственных значений 0 ± 1 , то ей наглавной ⎛диагонали предельной матрицыбудет соответствовать клетка размера 2 × 2:⎞×⎜⎟×⎟⎜⎟⎜0 1⎜⎟ −→ ⎜⎟ . (без доказательства)−1 0⎟→∞ ⎜⎜⎟..⎝⎠.0×Утверждение.Итерационный процесс останавливается, когда все элементы ниже главной диагонали, либо ниже побочной (в случае комплексно-сопряженных собственных значений) матрицы при некотором становятся равными нулю. Однако следует заметить, что в данном случае под нулем мы понимаем либо машинный ноль, либо число,меньшее некоторой заданной величины — необходимой точности вычисления.Замечание 1.12Замечание 2.QR-алгоритм применим к произвольной матрице .QR-алгоритм является очень затратным по необходимому числу операций и объему памяти, используемому для хранения промежуточных матриц.Замечание 3.§12Предварительное преобразование матрицы к ВПТФ.
Неухудшение ВПТФ при QR-алгоритмеЛемма 1.Пусть = , где имеет ВТФ, а имеет ВПТФ. Тогда имеет ВПТФ.Лемма 2. Пусть = , где — матрица с ВПТФ, а — матрица с ВТФ. Тогда —матрица с ВПТФ.Глава IIИнтерполирование и приближениефункцийГлава вырезана по причине отсутствия её на лекциях :)§13Постановка задачи интерполирования§14Интерполяционная формула Лагранжа§15Разделенные разности§16Интерполяционная формула Ньютона§17Интерполирование с кратными узлами.
Полином Эрмита§18Использование интерполяционного полинома Эрмита 3 ()для оценки погрешности квадратурной формулы Симпсона§19Наилучшее среднеквадратичное приближение функции§20Наилучшее среднеквадратичное приближение функций,заданных табличноГлава IIIЧисленное решение нелинейныхуравнений и систем нелинейныхуравнений§21Способы локализации корней нелинейного уравненияПостановка задачи. () = 0.(1)Рассмотрим функцию (), ∈ R, и уравнение () = 0 Пусть * — вещественный корень уравнения, и определена его окрестность радиуса , не содержащая других корнейуравнения: (* ) = { : | − * | < }, причем заданная функция () определена наэтой окрестности. Будем считать, что начальное приближение 0 ∈ (* ) задано.Тогда для нахождения численного решения уравнения в рассматриваемой окрестностинеобходимо построить последовательность { }, сходящуюся к корню * уравнения (1):lim→∞ ( ) = (* ) = 0.Первый прием локализации корняПусть задано разбиение сегмента [, ]: 6 0 < 1 < 2 < .
. . < 6 , и если длянекоторого = 1, выполняется условие (−1 ) ( ) < 0,(2)то на интервале (−1 , ) существует по крайней мере один корень уравнения (1) или числокорней на этом интервале нечетно. Если же выполняется условие (−1 ) ( ) > 0, = 1, ,то на каждом из интервалов (−1 , ) либо нет корней уравнения (1), либо их число четно.В случае выполнения условия (2) интервал (−1 , ) вновь разбивается на частичныеинтервалы, и для частичных интервалов повторяется описанная выше процедура, котораяв итоге позволит найти промежуток меньшей длины, содержащий корень.Второй прием локализации корняБолее регулярным способом отделения действительных корней является метод бисекции(деления пополам).Предположим, что на интервале (, ) расположен лишь один корень * уравнения (1).Тогда () и () имеют различные знаки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
