Н.И. Ионкин - Численные методы, страница 6

Домножим обе части уравнения (3) на − 2 слева:Доказательство.(︁)︁1 *= − 2(9) ∈ Z+ .121 +1 − + − 2 = 0.(10)1Введем вектор = 2 и перепишем задачу (10) через вектор :11 +1 − + − 2 − 2 = 0.Выразим +1 через :11 +1 = − − 2 − 2 = .Здесь матрица11 = − − 2 − 2(11)называется матрицей перехода от -й итерации к ( + 1)-й итерации вектора.40Глава I . Численные методы линейной алгебрыВ силу определения +1 и с учетом самосопряженности оператора верноравенство2121‖ +1 ‖ = ( +1 , +1 ) = ( 2 +1 , 2 +1 ) = ( +1 , +1 ) = ‖ +1 ‖ .Таким образом, чтобы доказать утверждение теоремы, достаточно получитьоценку‖ +1 ‖ 6 ‖ ‖.Покажем, что — самосопряженный оператор:(︁)︁(︁)︁(︁)︁11 *1 *1 * * = − − 2 − 2 = − − 2 * − 2 = .Пусть – собственные значения матрицы .

В силу самосопряженности матрицы в линейном пространстве существует ортонормированный базис изсобственных векторов оператора : = , ̸= , = 1, .(12)Покажем, что все собственные значения не превосходят по модулю :| | 6 , = 1, .Подставим выражение из (11) в (12) и умножим слева обе части равенства1на 2 :(︁ 1)︁11 2 − − 2 = 2 , = 1, .1Введем вектор = − 2 и перепишем это равенство в виде( − ) = , = 1, .Отсюда следует равенство: =1 − .Умножим левую и правую части этого равенства скалярно на вектор :(, ) =1 − (, ).Воспользуемся неравенством (8) из условия теоремы:1−1 − 1+(, ) 6(, ) 6(, ).§7. Оценка скорости сходимости итерационных методов41Из данных неравенств и неравенства ̸= следует, что (, ) > 0 и, следовательно,| | 6 , = 1, .Разложим вектор по ортонормированному базису { } из собственных векторов матрицы :∑︁()() = , = ( , ).=1Найдем разложение для +1 :∑︁ +1 = =() =∑︁() .=1=1Запишем равенство Парсеваля (7) для +1 :2‖ +1 ‖ = (︁∑︁() )︁2.=1В силу того, что | | 6 , = 1, , верно неравенство‖+1 22‖ 6 (︁∑︁)︁() 2= 2 ‖ ‖2 .=1Из этого неравенства следует оценка ‖ +1 ‖ 6 ‖ ‖, которая, как мы показали выше, эквивалентна утверждению теоремы.Замечание.Оценка (9) справедлива и в энергетической норме ‖·‖ .Пусть , — самосопряженные положительно определенные операторы, и пусть существуют 2 > 1 > 0, для которых выполняется условие1 6 6 2 .Следствие 1.Тогда, если = 0 =2,1 + 2то двухслойный итерационный метод решения системы уравнений сходится, и верна оценка‖+1 − ‖ 6 ‖ − ‖ ,(13)где =1−1+ ,=12 .42Глава I .

Численные методы линейной алгебрыДоказательство. Для того, чтобы воспользоваться теоремой 1, рассмотримнеравенство (8) из условия теоремы. Очевидно, что 1 = 1−и 2 = 1+ .Сложив эти равенства, получим1 + 2 =22., =1 + 2Вычитая из второго равенства первое, получим2 − 1 ==2= (1 + 2 ),1−12 − 1=, = .1 + 21+2Таким образом, оценка (13) выполнена с найденной выше константой .Сформулируем следующее следствие для метода простой итерации:+1 − + = , ∈ Z+ .Пусть — самосопряженный положительно определенныйоператор, а 1 и 2 — его минимальное и максимальное собственные значения:1 = min , 2 = max .Следствие 2.166Кроме того, пусть =21 +2 .166Тогда верна оценка‖+1 − ‖ 6 ‖ − ‖,где =1−1+ ,=12 .Доказательство следствия 2 очевидно.§8Исследование скорости сходимостиПТИМРассмотрим матричное уравнение вида = ,где || ≠ 0, ( × ), = (1 , 2 , . .

. , ) , = (1 , 2 , . . . , ) .Представим матрицу в виде = 1 + 2 ,(1)§8. Исследование скорости сходимостиПТИМ43где 1 — нижнетреугольная матрица, 2 — верхнетреугольная матрица:⎞⎛⎞⎛0.51112···10.5110···0⎜ 21⎜ 00.522 · · ·2 ⎟0.522 · · ·0 ⎟⎟⎜⎟⎜1 = ⎜ .,=⎟⎜.... ⎟ ...2.........⎝ .⎝ .....

⎠.. ⎠00· · · 0.512 · · · 0.5Очевидно, что такое представление существует для произвольной матрицы.Запишем каноническую форму попеременно-треугольного итерационногометода (ПТИМ):( + 1 )( + 2 )+1 − + = , > 0, > 0, ∈ Z+ .Обозначим = ( + 1 )( + 2 ).(о сходимости ПТИМ). Пусть — самосопряженный положительно определенный оператор и > 4 . Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении 0 .Теорема 1Доказательство.=2* :Раскроем скобки в выражении для , учитывая, что 1 = = ( + 2* )( + 2 ) = + (2* + 2 ) + 2 2* 2 = + + 2 2* 2 . (2)Очевидно, что = ( − 2* )( − 2 ) + 2.(3)Кроме того,(( − 2* )( − 2 ), ) = (( − 2 ), ( − 2 )) > 0.Тогда из равенства (3) следует неравенство(4) > 2.Учитывая условие теоремы ( > 4 ), получим, что > 2 и ПТИМ сходитсяпо теореме Самарского при любом начальном приближении 0 .Теорема 2 (о скорости сходимости ПТИМ).

Пусть — самосопряженныйположительно определенный оператор и числа > 0, Δ > 0 таковы, чтовыполняются неравенства > , 2* 2 6Δ.4(5)44Глава I . Численные методы линейной алгебрыПоложим)︃√ (︃ √√22ΔΔ√√, 1 =, 2 ==√ , =.1 + 224Δ+ ΔТогда ПТИМ сходится и имеет место оценка‖+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):4‖2 ‖2 ‖‖24Δ(, )‖‖2‖‖ 66= Δ‖‖2 .(, )4(, )2Таким образом, справедливо неравенство 6 Δ.При доказательстве будем опираться на следствие 1 из теоремы об оценкескорости сходимости итерационного метода общего вида.

Чтобы воспользоваться следствием 1 из теоремы об оценке скорости сходимости, найдем изусловия теоремы числа 1 и 2 такие, что1 6 6 2 .(7)§8. Исследование скорости сходимостиПТИМ45Из неравенства (4) ( > 2), полученного в ходе доказательства теоремыо сходимости ПТИМ следует оценка 6 2. Тогда можно положить в нера1венстве (7) 2 = 2 .Оценим выражение (2), воспользовавшись неравенствами (5):)︂(︂1Δ 21Δ 22 *.

= + + 2 2 6 + +=++44(︁)︁2 −1Тем самым неравенство (7) выполнено с постоянной 1 = 1 + + Δ.4Для нахождения максимально возможной скорости сходимости будем минимизировать функцию () (как известно, чем меньше , тем быстрее сходится метод):1 − ()1 ()() =, () =,1 + ()2 ()что эквивалентно минимизации функции ():(︂)︂2 ()11Δ () ==1++.1 ()24Для нахождения экстремальных точек найдем производную () и приравняем ее к нулю:(︂)︂121 Δ′− 2= 0 ⇒ = 0 = √ .

() =2 4 ΔУчтем, что > 0, и проверим, что точка 0 доставляет минимум функции (), найдя знак второй производной функции в этой точке: ′′ () =1> 0. 3Подставим 0 в выражения для 1 , 2 , :1 =11+√2Δ+Δ 44 Δ=2)︃√ (︃ √√1 ΔΔ√ =√√= √,2+ √2Δ2 Δ+2 Δ+ 1=2 =20Отсюда√Δ.4)︃√ (︃ √√1 ()4Δ2 √√√() ==√=√2 ()Δ 2Δ+ Δ+ 46Глава I . Численные методы линейной алгебрыи√√ ⎫√√√√2 Δ− ⎪1− Δ−1−⎪⎪√√1− = 1− √=√√ ===√⎬√ ,Δ+ Δ+ 1+1+3 Δ+3 ⇒√√√2 Δ + 3 ⎪⎪√ = √√ ⎪1+ = 1+ √⎭(Δ ̸= 0).=ΔΔ+ Δ+ Исходя из полученных соотношений и следствия 1, получаем оценку‖+1 − ‖ 6 ‖ − ‖ .Таким образом, теорема 2 доказана.Покажем, что ПТИМ сходится на порядок быстрее метода простой итерации, метода Зейделя и метода Якоби.Число итераций, необходимое для достижения заданной точности > 0равно[︃]︃ln 1,0 () =ln 1где [] означает целую часть числа , а ln 1 — скорость сходимости итерационного метода.

В практических задачах, велико, отношение = Δ(︀ −2когда)︀часто является величиной порядка O .Оценим скорость сходимости ПТИМ:√√√1+3 (1 + 3 )(1 + )1√=≈ 1 + 4 ,√ =1− 1−ln(︀)︀(︀ )︀1√≈ ln(1 + 4 ) = O −1 , 0 () = O .Оценим скорость сходимости метода простой итерации:=1−1− 11+(1 + )2=,==≈ 1 + 2,1+1+ 1−1 − 2ln(︀)︀(︀ )︀1≈ ln(1 + 2) = O −2 , 0 () = O 2 .Таким образом, метод простой итерации сходится на порядок медленнее, чемПТИМ. Методы Якоби и Зейделя имеют тот же порядок сходимости, что иметод простой итерации.§9.

Методы решения задач на собственные значения§947Методы решения задач на собственные значенияРассмотрим задачу поиска собственных значений, которая состоит в нахождении чисел и векторов , удовлетворяющих уравнению = , ̸= ,где — вещественная матрица порядка ( × ). Число называется собственным значением матрицы , а — соответствующим ему собственнымвектором. У любой вещественной матрицы порядка ( × ) существует, сучетом кратности, ровно собственных значений, вообще говоря, комплексных.Собственный вектор определяется с точностью до константы ̸= 0.

В вычислительных методах собственные векторы обычно нормируют с условием‖‖ = 1, чтобы избежать быстрого накопления ошибок округления.Задача поиска собственных значений эквивалентна задаче нахождениякорней характеристического многочлена матрицы :| − | = + −1 −1 + . . . + 1 + 0 = 0,где ∈ R, = 0, , ̸= 0. Это уравнение имеет общее решение в радикалахтолько при 6 4, в реальных же задачах может быть порядка 105 или 106и выше. Таким образом, при больших задачу поиска собственных значений,за редким исключением, можно решить только численными методами.Собственные значения необходимы для оценки скорости сходимости итерационных методов решения систем линейных уравнений. При этом обычнодостаточно найти минимальное и максимальное по модулю собственные значения.

Таким образом, различают два вида проблем, связанных с поискомсобственных значений матрицы:1. Частичная проблема собственных значений, которая заключается в нахождении отдельных собственных значений.2. Полная проблема собственных значений, которая заключается в нахождении всего спектра матрицы.Очевидно, что частичная проблема является более простой, чем полная проблема.Степенной методРассмотрим частичную проблему собственных значений. Будем искать собственный вектор по формуле (см. [6], гл.VI, §4)+1 = , ∈ Z+ , 0 задано.(1)48Глава I . Численные методы линейной алгебрыПусть { }=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Покажем, что при выполнении условий A) – C) степеннойметод сходится по направлению к собственному вектору матрицы , отвечающему максимальному по модулю собственному значению.Из рекуррентной формулы (1) получим:Доказательство.