main (1160440), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

, ). Таким образом, мы получили, что(, ) < (2, ).Из этого неравенства следует, что 2 > .Следовательно, выполняется условие следствия 1, и итерационный метод Якоби сходится при любом начальном приближении.Задача. Пусть = * > 0. Доказать, что > 0, = 1, .Следствие 3. Пусть = * > 0. Тогда метод Зейделя сходится в среднеквадратичнойнорме при любом начальном приближении 0 .Доказательство. Из условия теоремы Самарского следует, что для сходимости методаЗейделя достаточно выполнения неравенства − > 0.2(14)Представим матрицу в виде = 1 + + 2 . В канонической записи метода Зейделя = 1, = 1 + . Тогда достаточное условие (14) преобразуется к виду + 1 −1 + + 2> 0.2§7. Оценка скорости сходимости итерационных методов27И, следовательно, + 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)В методе простой итерации = . Следовательно, условие (17) преобразуется к виду − > 0.2(18)Неравенство (18) равносильно неравенству − 2 > 0, которое справедливо, если1 − 2 > 0.2Из положительности параметра следует, что для сходимости метода простой итерациидостаточно выполнения условия20< < .2§7Оценка скорости сходимости итерационных методовРассмотрим матричное уравнение вида = ,(1)где || ̸= 0, ( × ), = (1 , 2 , .

. . , ) , = (1 , 2 , . . . , ) и двухслойный стационарный метод решения этого уравнения:+1 − + = ,(2)28Глава 1. Численные методы линейной алгебрыгде ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица размера ( × ).Введем погрешность = − . Тогда из уравнения (2) получим однородную задачу: +1 − + = 0, ∈ Z+ , 0 = 0 − .(3)Предположим, что выполняется оценка‖ +1 ‖ 6 ‖ ‖,0 < < 1.(4)Тогда можно говорить о скорости сходимости итерационного метода (2) в зависимостиот параметра . Применив эту оценку раз для , получим:‖ ‖ 6 ‖ 0 ‖.(5)При 0 < < 1 видно, что ‖ ‖ −→ 0. Заметим, что чем ближе параметр к нулю, тем выше→∞скорость сходимости метода (2).

Кроме того, оценка (4) позволяет посчитать необходимоеколичество итераций для достижения заданной точности > 0:‖ − ‖ 6 ‖0 − ‖(6)Из неравенств (5) и (6) получим11> . 6 ,Прологарифмируем обе части второго неравенства и выразим :>ln 1.ln 1Таким образом, для достижения заданной точности достаточно провести количество итераций, равное]︃[︃ln 1, где [] — целая часть числа .0 () =ln 1Определение. Величина ln1называется скоростью сходимости итерационного метода.Пусть — вещественное линейное пространство размерности . Введем в скалярноепроизведение и среднеквадратичную норму:(, ) =∑︁ ,=1‖‖ =√︀(, ).Пусть = * > 0. Введем энергетическую норму, порождаемую оператором :√︀‖‖ = (, ).В пространстве существует ортонормированный базис { } из собственных векторовоператора : = , ̸= , = 1, ,§7.

Оценка скорости сходимости итерационных методов{︃1 при = ,( , ) = =0 при ̸= ,29, = 1, .Тогда любой вектор ∈ можно однозначно разложить по этому базису:=∑︁ , = (, ).=1Кроме того, в линейном пространстве с заданной в нем нормой и ортонормированнымбазисом выполняется равенство Парсеваля:2‖‖ =∑︁2 , ∈ .(7)=1Теорема 1 (об оценке скорости сходимости).

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

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

Оценка скорости сходимости итерационных методов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 .Таким образом, МПИ сходится на порядок медленнее, чем ПТИМ.

Характеристики

Список файлов лекций