Н.И. Ионкин - Численные методы (1163659), страница 5
Текст из файла (страница 5)
Получим однородное уравнение: +1 − + = 0,(4)32Глава I . Численные методы линейной алгебрыгде ∈ Z+ , 0 = 0 − .Приступим к исследованию задачи (4). Выразим ( + 1)-ю итерацию через -ю с учетом того, что для матрицы существует обратная. Домножимуравнение (4) на −1 слева: +1 − + −1 = 0.Выразим из уравнения погрешность на ( + 1)-й итерации: +1 = − −1 = ( − −1 ) = .Таким образом, мы получили матрицу , которая связывает погрешность напредыдущей итерации с погрешностью на следующей: = − −1 .(5)Матрица из равенства (5) называется матрицей перехода от -й итерации к ( + 1)-й.Определение.Итерационный метод (2) решения системы (1) сходится прилюбом начальном приближении тогда и только тогда, когда все собственные значения матрицы перехода по модулю меньше единицы.
(Без доказательства, доказательство см. [1], стр.92).Теорема 1.Таким образом, сходимость итерационного метода (2) всецело зависит отсвойств матрицы S, а именно, от ее спектра.Заметим, что данная теорема практически неприменима, так как задача нахождения полного спектра матрицы аналитически решается крайнередко.Приступим к рассмотрению вопроса сходимости итерационного метода.В дальнейшем будем считать, что линейное пространство задано над полемR вещественных чисел.(теорема Самарского). Пусть — самосопряженный положительно определенный оператор, — положительное вещественное число ивыполнено операторное неравенство − > 0.(6)2Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичной норме при любом начальном приближении:⎯⎸∑︁)︁2⎸ (︁ ‖ − ‖ = ⎷ − −→ 0, ∀0 .Теорема 2=1→∞§6.
Теоремы о сходимости итерационных методов33Пусть = − . Введем числовую последовательность =Покажем, что { } — невозрастающая и ограниченная снизупоследовательность. Для этого рассмотрим +1 :Доказательство.( , ).+1 = ( +1 , +1 ) = ( , ) = ((− −1 ) , (− −1 ) ). (7)Воспользуемся линейностью скалярного произведения и преобразуем правуючасть равенства:( , ) − ( , −1 ) − ( −1 , ) + 2 ( −1 , −1 ). (8)В силу того, что оператор — самосопряженный ( = * ), получим(︀)︀ (︀)︀ (︀)︀ −1 , = −1 , * = , −1 .Преобразуем выражение (8): − 2 ( , −1 ) + 2 ( −1 , −1 ) =(︁(︁)︁ )︁= − 2 − −1 , −1 .2Подставив найденное выражение в равенство (7), получим тождество)︁(︁(︁+1 − )︁(9)+ 2 − −1 , −1 = 0,2(︀)︀в котором оператор − 2 положителен по условию. Следовательно, второе слагаемое тождества неотрицательно.Отсюда следует, что +1 6 ,что и означает монотонность последовательности { }.
Так как > 0, то = ( , ) > 0.У невозрастающей последовательности { }, все члены которой неотрицательны, по теореме Вейерштрасса существует предел :lim = .→∞Для дальнейшего доказательства нам понадобится свойство положительно определенного линейного оператора, которое мы сформулируем в видезадачи.Пусть — вещественное линейное пространство, — положительный линейный не обязательно самосопряженный оператор в . Доказать, что∃ > 0 : (, ) > ‖‖2 , ∀ ∈ .(10)Задача.34Глава I .
Численные методы линейной алгебрыВоспользуемся свойством (10): существует константа > 0 такая, что(︁(︁)︁ )︁ − −1 , −1 > ‖ −1 ‖2 > 0.(11)2Введем вектор : = −1 .(12)Устремим к бесконечности в равенстве (9):(︁(︁)︁ )︁−+ 2 lim − , = 0.→∞2Устремим теперь к бесконечности в неравенстве (11) и примем во вниманиеполученное равенство:0 6 lim ‖ ‖2 6 0.→∞Получим, чтоlim ‖ ‖ = 0.→∞Выразим погрешность на -й итерации из равенства (12): = −1 .Оператор −1 существует вследствие предположения > 0. Очевидно, что‖ ‖ 6 ‖−1 ‖‖ ‖, но ‖−1 ‖ не зависит от . Следовательно,lim ‖ ‖ = lim ‖ − ‖ = 0.→∞→∞Так как в ходе доказательства мы не использовали начальное приближение, то оно может быть произвольным.Пусть = * > 0. Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении, если выполненонеравенство:2 > ,Следствие 1.где = 1 + + 2 , = diag(11 , 22 , .
. . , ).В методе Якоби = 1, а = . По теореме Самарскогометод сходится, если − > 0.2В нашем случае1 − > 0,2а это выполняется в силу условия 2 > . Следовательно, метод Якобисходится в среднеквадратичной норме при любом начальном приближении.Доказательство.§6. Теоремы о сходимости итерационных методов35Пусть положительная симметричная матрица ( = * >> 0) является матрицей со строгим диагональным преобладанием:Следствие 2.∑︁ >| |, = 1, .=1,̸=Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении 0 .Доказательство.Рассмотрим квадратичную форму с матрицей :(, ) =∑︁ 6,=1∑︁| | | | | |.(13),=1Для дальнейшей оценки квадратичной формы (13) воспользуемся неравен22ством 6 +2 :(, ) 61 ∑︁1 ∑︁| | | |2 +| | | |2 .22,=1,=1Преобразуем правую часть неравенства с учетом того, что матрица является симметричной (| | = | |):∑︁1 ∑︁1 ∑︁22| | | | +| | | | =| | | |2 .22,=1,=1,=1Вынесем суммирование по индексу и воспользуемся свойством диагонального преобладания матрицы :⎛⎞∑︁∑︁∑︁2⎝⎠| | +| | <22 = (2, ),=1=1,̸==1где = diag(11 , 22 , .
. . , ). Таким образом, мы получили, что(, ) < (2, ).Из этого неравенства следует, что 2 > .Следовательно, выполняется условие следствия 1, и итерационный методЯкоби сходится при любом начальном приближении.Задача.Пусть матрица = * > 0. Доказать, что > 0, = 1, .36Глава I . Численные методы линейной алгебрыПусть = * > 0. Тогда метод Зейделя сходится в среднеквадратичной норме при любом начальном приближении 0 .Следствие 3.Из условия теоремы Самарского следует, что для сходимости метода Зейделя достаточно выполнения неравенстваДоказательство. − > 0.2(14)Представим матрицу в виде = 1 ++2 .
В канонической записи методаЗейделя = 1, = 1 + . Тогда достаточное условие (14) преобразуетсяк виду1 + + 2 + 1 −> 0.2И, следовательно, + 1 − 2 > 0.(15)Запишем это неравенство в виде(, ) + (1 , ) − (2 , ) > 0, ̸= .Так как = * , то 2* = 1 . Тогда(2 , ) = (, 2* ) = (, 1 ) = (1 , ).Следовательно, неравенство (15) принимает вид(, ) > 0, ̸= .(16)Если матрица симметричная и положительно определенная, то все еедиагональные элементы больше нуля (см.
задачу). Следовательно, матрица также является положительно определенной, откуда следует неравенство(16).Следствие 4.Пусть = * > 0, 2 = max > 0. Если 0 < <16622 ,тометод простой итерации сходится в среднеквадратичной норме при любомначальном приближении 0 .Доказательство. Из условия теоремы Самарского следует, что для того,чтобы метод простой итерации сходился в среднеквадратичной норме прилюбом начальном приближении, достаточно выполнения неравенства − > 0.2(17)§7. Оценка скорости сходимости итерационных методов37В методе простой итерации = .
Следовательно, условие (17) преобразуется к виду − > 0.(18)2Неравенство (18) выполнено, если − 2 > 0, что справедливо, если1 − 2 > 0.2Из положительности параметра следует, что для сходимости метода простой итерации достаточно выполнения условия0< <§72.2Оценка скорости сходимости итерационных методовРассмотрим матричное уравнение вида(1) = ,где || ̸= 0, ( × ), = (1 , 2 , . . .
, ) , = (1 , 2 , . . . , ) и двухслойный стационарный метод решения этого уравнения:+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица размера ( × ).Введем погрешность = − . Тогда из уравнения (2) получим задачу: +1 − + = 0, ∈ Z+ , 0 = 0 − .Предположим, что выполняется оценка‖ +1 ‖ 6 ‖ ‖,0 < < 1.(3)(4)Тогда можно говорить о скорости сходимости итерационного метода (2) в зависимости от параметра . Применив эту оценку раз получим:‖ ‖ 6 ‖ 0 ‖.(5)38Глава I .
Численные методы линейной алгебрыПри 0 < < 1 видно, что ‖ ‖ −→ 0. Заметим, что чем ближе параметр→∞ к нулю, тем выше скорость сходимости метода (2). Кроме того, оценка (5)позволяет посчитать необходимое число итераций для достижения заданнойточности > 0:‖ − ‖ 6 ‖0 − ‖(6)Из неравенств (5) и (6) получим 6 ,11> .Прологарифмируем обе части второго неравенства:>ln 1.ln 1Таким образом, для достижения заданной точности достаточно провестичисло итераций, равное[︃]︃ln 10 () =, где [] — целая часть числа .ln 1Определение.онного метода.Величина ln1называется скоростью сходимости итерациПусть — вещественное линейное пространство размерности .
Введемв скалярное произведение и среднеквадратичную норму:(, ) =∑︁ , ‖‖ =√︀(, ).=1Пусть = * > 0. Введем энергетическую норму, порождаемую оператором:√︀‖‖ = (, ).В пространстве существует ортонормированный базис { } из собственныхвекторов оператора : = , ̸= , = 1, ,{︃1 при = ,( , ) = =, = 1, .0 при ̸= ,§7. Оценка скорости сходимости итерационных методов39Тогда любой вектор ∈ можно однозначно разложить по этому базису:=∑︁ , = (, ).=1Кроме того, в линейном пространстве с заданной в нем нормой и ортонормированным базисом выполняется равенство Парсеваля:2‖‖ =∑︁2 ,(7) ∈ .=1(об оценке скорости сходимости). Пусть = * > 0, = * >> 0. Пусть также существует число , 0 < < 1, такое, что выполненооператорное неравенство:Теорема 11−1+66.(8)Тогда для погрешности итерационного метода (2) решения системы (1)справедлива оценка:‖ +1 ‖ 6 ‖ ‖ ,1Так как = * > 0, то существует матрица − 2 =1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
