Численные методы. Ионкин (2013) (1160444), страница 5
Текст из файла (страница 5)
Следовательно, второе слагаемоетождества неотрицательно.Отсюда следует, что +1 6 , что и означает монотонностьпоследовательности { }.У невозрастающей последовательности { }, все члены которой неотрицательны, потеореме Вейерштрасса существует предел :lim = .→∞Для дальнейшего доказательства нам понадобится свойство положительно определенного линейного оператора, которое мы сформулируем в виде задачи.Задача. Пусть — вещественное линейное пространство, — положительный линейный оператор в .
Доказать, что∃ > 0 : (, ) > ‖‖2 , ∀ ∈ .(10)§6. Теоремы о сходимости итерационных методов25Воспользуемся свойством (10): существует константа > 0 такая, что(︁(︁)︁ )︁ − −1 , −1 > ‖ −1 ‖2 > 0.2(11)Введем вектор : = −1 .(12)Устремим к бесконечности в равенстве (9):)︁(︁(︁− )︁+ 2 lim − , = 0.→∞2Устремим теперь к бесконечности в неравенстве (11) и примем во внимание полученноеравенство:0 6 lim ‖ ‖2 6 0.→∞Получим, чтоlim ‖ ‖ = 0.→∞Выразим погрешность на -ой итерации из уравнения (12): = −1 .Так как норма произведения операторов не превосходит произведения их норм, а матрица−1 не зависит от номера итерации, то получим, что погрешность стремится к нулюпри , стремящемся к бесконечности:‖ ‖ 6 ‖−1 ‖‖ ‖ −→ 0.→∞Следовательно,lim ‖ ‖ = lim ‖ − ‖ = 0.→∞→∞Так как в ходе доказательства мы не использовали начальное приближение, то ономожет быть произвольным.Следствие 1.
Пусть = * > 0. Тогда метод Якоби сходится в среднеквадратичнойнорме при любом начальном приближении, если выполнено неравенство:2 > ,где = 1 + + 2 , = diag(11 , 22 , . . . , ).Доказательство. В методе Якоби = 1, а = . По теореме Самарского метод сходится,если − > 0.2В нашем случае1 − > 0,2а это выполняется в силу условия 2 > .
Следовательно, метод Якоби сходится в среднеквадратичной норме при любом начальном приближении.26Глава 1. Численные методы линейной алгебрыСледствие 2. Пусть самосопряженная положительно определенная матрица = * >0 является матрицей со строгим диагональным преобладанием:∑︁ >| |, = 1, .=1,̸=Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении 0 .Доказательство. Рассмотрим квадратичную форму с матрицей :(, ) =∑︁ 6,=1∑︁| | | | | |.Для дальнейшей оценки квадратичной формы (13) воспользуемся неравенством 6(, ) 6(13),=12 +22 :1 ∑︁1 ∑︁| | | |2 +| | | |222,=1,=1Преобразуем правую часть неравенства с учетом того, что матрица является самосопряженной (| | = | |):∑︁1 ∑︁1 ∑︁| | | |2 +| | | |2 =| | | |2 .22,=1,=1,=1Вынесем суммирование по индексу и воспользуемся свойством диагонального преобладания матрицы :⎛⎞∑︁∑︁∑︁| |2 ⎝ +| |⎠ <22 = (2, ),=1=1,̸==1где = diag(11 , 22 , .
. . , ). Таким образом, мы получили, что(, ) < (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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
