Численные методы. Ионкин (2013) (1160444), страница 6
Текст из файла (страница 6)
Оценка скорости сходимости итерационных методов31Замечание. Оценка (9) справедлива и в энергетической норме ‖·‖ .Следствие 1. Пусть , — самосопряженные положительно определенные операторы,и пусть существуют 2 > 1 > 0, для которых выполняется условие1 6 6 2 .Тогда, если = 0 =2,1 + 2то двухслойный итерационный метод решения системы уравнений сходится, и вернаоценка‖+1 − ‖ 6 ‖ − ‖ ,где =1−1+ ,=(13)12 .Доказательство. Для того, чтобы воспользоваться теоремой 1, рассмотрим неравенство (8)1+из условия теоремы.
Очевидно, что 1 = 1− и 2 = . Сложив эти равенства, получим1 + 2 =22, =.1 + 2Вычитая из второго равенства первое, получим2 − 1 ==2= (1 + 2 ),2 − 11−1=, = .1 + 21+2Таким образом, оценка (13) выполнена с найденной выше константой .Сформулируем следующее следствие для метода простой итерации:+1 − + = , ∈ Z+ .Следствие 2. Пусть — самосопряженный положительно определенный оператор, а 1и 2 — его минимальное и максимальное собственные значения:1 = min , 2 = max .166Кроме того, пусть =21 +2 .166Тогда верна оценка‖+1 − ‖ 6 ‖ − ‖,где =1−1+ ,=12 .Доказательство следствия 2 очевидно.32§8Глава 1.
Численные методы линейной алгебрыИсследование скорости сходимости ПТИМРассмотрим матричное уравнение вида = ,(1)где || ≠ 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) .Представим матрицу в виде = 1 + 2 ,где 1 — нижнетреугольная⎛0.5110⎜ 210.522⎜1 = ⎜ ....⎝ ..12матрица, 2 — верхнетреугольная матрица:⎞⎛···00.51112···⎜ 0···0 ⎟0.5···22⎟⎜.... ⎟ , 2 = ⎜ .......⎝ .... ⎠· · · 0.50012...⎞⎟⎟⎟.⎠· · · 0.5Очевидно, что такое представление существует для произвольной матрицы .Запишем каноническую форму попеременно-треугольного итерационного метода (ПТИМ):( + 1 )( + 2 )+1 − + = , > 0, > 0, ∈ Z+ .Обозначим = ( + 1 )( + 2 ).Теорема 1 (о сходимости ПТИМ). Пусть — самосопряженный положительно определенный оператор и > 4 . Тогда ПТИМ сходится в среднеквадратичной норме при любомначальном приближении 0 .Доказательство.
Раскроем скобки в выражении для , учитывая, что 1 = 2* : = ( + 2* )( + 2 ) = + (2* + 2 ) + 2 2* 2 = + + 2 2* 2 .(2)Очевидно, что = ( − 2* )( − 2 ) + 2.(3)Кроме того,(( − 2* )( − 2 ), ) = (( − 2 ), ( − 2 )) > 0.Тогда из уравнения (3) следует неравенство > 2.(4)Учитывая условие теоремы ( > 4 ), получим, что > 2 и ПТИМ сходится по теоремеСамарского при любом начальном приближении 0 .Теорема 2 (о скорости сходимости ПТИМ). Пусть — самосопряженный положительноопределенный оператор и числа > 0, ∆ > 0 таковы, что выполняются неравенства > , 2* 2 6Положим∆.4)︃√ (︃ √√22∆∆√√=√ , =, 1 =, 2 =.+24∆+ ∆12(5)§8. Исследование скорости сходимости ПТИМ33Тогда ПТИМ сходится и имеет место оценка‖+1 − ‖ 6 ‖ − ‖ ,где =√1− √1+3 ,=Δ.Доказательство.
Покажем, что из неравенств (5) следует 6 1. Рассмотрим второе неравенство и воспользуемся определением сопряженного оператора:2* 2 6∆∆ ⇒ (2* 2 , ) = (2 , 2 ) = ‖2 ‖2 6 (, ).44(6)Рассмотрим первое неравенство: > ⇒ (, ) > ‖‖2 .Очевидно, что из представления = 1 + 2 = 2* + 2 следует равенство(, ) = (2* , ) + (2 , ) = 2(2 , ).Тогда предположим, что — ненулевой вектор, и получим‖‖2 6 (, ) =(, )24(2 , )2=.(, )(, )Воспользуемся неравенством Коши-Буняковского и неравенством (6):‖‖2 64‖2 ‖2 ‖‖24∆(, )‖‖26= ∆‖‖2 .(, )4(, )Таким образом, справедливо неравенство 6 ∆.При доказательстве будем опираться на следствие 1 из теоремы об оценке скоростисходимости итерационного метода общего вида.
Чтобы воспользоваться следствием 1 изтеоремы об оценке скорости сходимости, найдем из условия теоремы 1 и 2 такие, что1 6 6 2 .(7)Из неравенства (4) ( > 2), полученного в ходе доказательства теоремы о сходимости1ПТИМ следует оценка 6 2. Тогда можно положить в неравенстве (7) 2 = 2.Оценим выражение (2), воспользовавшись неравенствами (5):(︂)︂1∆ 2∆ 212 * = + + 2 2 6 + +=++.44(︁)︁2 −1Тогда положим в неравенстве (7) 1 = 1 + + Δ.4Для нахождения максимально возможной скорости сходимости будем минимизироватьфункцию () (как известно, чем меньше , тем быстрее сходится метод):() =1 − ()1 (), () =,1 + ()2 ()что эквивалентно минимизации функции ():(︂)︂2 ()11∆ () ==1++→ .1 ()2434Глава 1. Численные методы линейной алгебрыДля нахождения экстремальных точек найдем производную () и приравняем ее к нулю:(︂)︂21 ∆1′= 0 ⇒ = 0 = √ .
() =− 22 4 ∆Учтем, что > 0, и проверим, что точка 0 доставляет минимум функции (), найдязнак второй производной функции в этой точке: ′′ () =1> 0. 3Подставим 0 в выражения для 1 , 2 , :)︃√ (︃ √√1 ∆∆√ =√√1 = 1= 2= √Δ 4√2√222 ∆+2 ∆+ + Δ + Δ + 4 Δ√1∆2 ==204)︃√ (︃ √√42 1 ()∆√√√=√=√() =2 ()∆ 2∆+ ∆+ √√ ⎫√2 ∆− ⎪√√⎪√ =√√ ⎪1− = 1− √√⎬1− ∆− 1−∆+ ∆+ √√==(∆ ̸= 0).⇒=√√√√ ,=⎪1+1+3∆∆+3∆ + 3 ⎪2 √ = √√ ⎪1+ = 1+ √⎭∆+ ∆+ Исходя из полученных соотношений и следствия 1, получаем оценку1‖+1 − ‖ 6 ‖ − ‖ .Таким образом, теорема доказана.Покажем, что ПТИМ сходится на порядок быстрее метода простой итерации (МПИ),метода Зейделя (МЗ) и метода Якоби (МЯ).Число итераций, необходимое для достижения заданной точности > 0 равно[︃]︃ln 10 () =,ln 1где [] означает целую часть числа , а ln 1 — скорость сходимости итерационного метода.(︀)︀В практических задачах часто является величиной порядка O −2 .Оценим скорость сходимости ПТИМ:√√√1+3 (1 + 3 )(1 + )1√=≈ 1 + 4 ,√ =1− 1−(︀)︀(︀ )︀1√≈ ln(1 + 4 ) = O −1 , 0 () = O .Оценим скорость сходимости МПИ:ln1−1− 11+(1 + )2=,==≈ 1 + 2,1+1+ 1−1 − 2(︀)︀(︀ )︀1ln ≈ ln(1 + 2) = O −2 , 0 () = O 2 .Таким образом, МПИ сходится на порядок медленнее, чем ПТИМ.
МЯ и МЗ имеют тотже порядок сходимости, что и МПИ.=§9. Методы решения задач на собственные значения§935Методы решения задач на собственные значенияРассмотрим задачу поиска собственных значений, которая состоит в нахождении чисел и векторов , удовлетворяющих уравнению = , ̸= ,где — вещественная матрица порядка ( × ). называется собственным значениемматрицы , а — соответствующим ему собственным вектором. У любой вещественнойматрицы порядка ( × ) существует ровно собственных значений, вообще говоря, комплексных.Собственный вектор определяется с точностью до константы ̸= 0.
В вычислительныхметодах собственные векторы обычно нормируют, чтобы избежать быстрого накопленияошибок округления. Далее, в описаниях итерационных методов решения задач на поисксобственных значений заданной матрицы, мы будем предполагать, что на каждой итерации значение вектора , приближающего искомый собственный вектор, нормируетсяс условием ‖ ‖ = 1Задача поиска собственных значений эквивалентна задаче нахождения корней характеристического многочлена матрицы :| − | = + −1 −1 + .
. . + 1 + 0 = 0,где ∈ R, = 0, , ̸= 0. Это уравнение имеет общее решение в радикалах только при 6 4, в реальных же задачах может быть порядка 105 или 106 и выше. Таким образом,при больших задачу поиска собственных значений можно решить только численнымиметодами.Собственные значения необходимы для оценки скорости сходимости итерационных методов решения систем линейных уравнений.
При этом обычно достаточно найти минимальное и максимальное по модулю собственные значения. Таким образом, различают два видапроблем, связанных с поиском собственных значений матрицы:1. Частичная проблема собственных значений, которая заключается в нахождении некоторых собственных значений.2. Полная проблема собственных значений, которая заключается в нахождении всегоспектра матрицы.Очевидно, что частичная проблема является более простой, чем полная проблема.Степенной методРассмотрим частичную проблему собственных значений. Будем искать собственный векторпо формуле+1 = , ∈ Z+ , 0 задано.(1)Пусть { }=1 — собственные значения матрицы , среди которых могут быть повторяющиеся. Упорядочим их по неубыванию модулей:|1 | 6 |2 | 6 .
. . 6 | |.Будем доказывать сходимость степенного метода при выполнении трех условий:A) В пространстве R существует базис { } из собственных векторов матрицы .36Глава 1. Численные методы линейной алгебры⃒⃒⃒ −1 ⃒B) ⃒ ⃒ < 1.C) 0 = 1 1 + 2 2 + . . . + , где ̸= 0.Утверждение. Пусть вещественная матрица (×) такова, что выполнены условияA) – C). Тогда степенной метод для матрицы сходится по направлению к собственномувектору, отвечающему максимальному по модулю собственному значению: −→ .→∞Кроме того, для последовательности{︁}︁() , заданной одной из формул() =() =+1,( , )( , )справедлива следующая оценка сходимости к :(︃(︂)︂ )︃−1 () − = O.Доказательство. Покажем, что при выполнении условий A) – C) степенной метод сходится к собственному вектору матрицы , отвечающему максимальному по модулю собственному значению.Из рекуррентной формулы (1) получим: = 0 , ∈ N.Воспользуемся условиями A), C) и разложим -ую итерацию по базису из собственныхвекторов { } матрицы : 0 = =∑︁=1 =∑︁ = + −1 −1 −1 + .
. . + 1 1 1 .=1В силу условия C) ̸= 0. Кроме того, поскольку у матрицы существует хотя бы одноненулевое собственное значение, то максимальное по модулю из них гарантированно неравно нулю: ̸= 0. Поделив равенство на , получим:(︂)︂(︂)︂−1 −1 1 1 −1 + . . .
+1 .= + Перейдя к пределу при → ∞ и учитывая условие B), получим, что сходится по направлению к :lim = .→∞Рассмотрим два способа вычисления максимального по модулю собственного значенияматрицы . Первый способ состоит в вычислении отношения -ых координат ( + 1)-ой и-ой итераций.() = 1, , = 1 1 1 + . . . + (),§9. Методы решения задач на собственные значения37()()+1= 1 +11 + . . . + +1 ,1 = 1, .()Здесь — -ая координата вектора , = 1, .()()() =+1= ,(2)()()+1+1 +11 + −1 −1 −1 + . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
