Численные методы. Соснин (2005) (1160462), страница 4

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

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

Кроме того, так как мы берем q =1−1+γ1γ2γ1γ2,то наилучшим вариантом будет как раз λmin (B −1 A) = λmax (B −1 A).Все, мы закончили с главной теоремой этого параграфа, пора построить пример использованиянаших методов.Примечание. Выполнение неравенства (1.27) при γ1 = λmin (B −1 A), γ2 = λmax (B −1 A) следует извозможности построения в данном линейном пространстве базиса из собственных векторов.Модельная задача. Сравнение скорости сходимости различных итерационных методовРассмотрим краевую задачу:−u00 (x) = f (x), 0 < x < 1;u(0) = u(1) = 0.Найдем ее решение, используя численные методы. Для этого сначала разделим отрезок [0; 1] на Nравных промежутков длины h = N1 , обозначив границы отрезков как xi :0 = x0 < x1 < x2 < .

. . < xN = 1;h = xi+1 − xi .20Глава 1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙВоспользуемся тем, что u00 (xi ) можно приблизить 2-й разностной производной:u00 (xi ) ≈u(xi+1 ) − 2u(xi ) + u(xi−1 )h2defПусть y(x) — приближение нашей функции. Потребуем, чтобы yi = y(xi ) = u(xi ).

Тогда, зная, чтоu (xi ) = f (xi ), и используя разностное приближение, получим такую систему уравнений относительнозначений y в узлах сетки:00−y(xi+1 ) − 2y(xi ) + y(xi−1 )= f (xi ),h2i = 1, N − 1.Обозначим fi = f (xi ). Из краевых условий можно получить, что y0 = yN = 0. Тогда получимтакую систему: − yi+1 − 2yi + yi−1 = fi , i = 1, N − 1;h2(1.28)y0 = yN = 0.Понятно, что решив ее, мы получим приближенные значения u(xi ) = yi .

Теперь обозначимY = (y1 , y2 , . . . , yN −1 )T ;F = (f1 , f2 , . . . , fN −1 )T .Тогда систему (1.28), использовав значения y0 и yN , можно переписать внияAY = F,21− h22 −1h2 1..2−.0 2−1 2 . . .h2 h1..........где A = = 2..... h 0 ...0 . . . . . . − h12 12 − 2hh2виде матричного уравне(1.29)....... −1−1 20Легко видеть, что A = AT . Покажем, что A > 0 — для этого обоснуем положительность всехсобственных значений.Утверждается, что уравнение для поиска собственных значений Aξ = λξ в каком-то смысле эквивалентно задаче Штурма-Лиувилля:X 00 + λX = 0, 0 < x < 1;X(0) = X(1) = 0,решением которой будут собственные функции Xm (x) = sin πmx.

Отсюда делается вывод, что длясобственных значений матрицы A справедлива формула:λm4= 2hπmhsin22,m = 1, N − 1.Таким образом, все λm положительны и матрица A положительно определена. Легко проверить,что справедлива следующая цепочка неравенств:0 < λ1 < λ2 < . . . < λN −1 ,1.5. ПОПЕРЕМЕННО-ТРЕУГОЛЬНЫЙ ИТЕРАЦИОННЫЙ МЕТОД21224πhπh4причем λ1 = λmin = 2 sinи λN −1 = λmax = 2 cos. ҷ Будем решать уравнение (1.29)h2h2методом простой итерации:xk+1 − xk+ Axk = f.τДля него справедлива теорема 1.3 о скорости сходимости, так как A = AT > 0 (по доказанному) иB = B −1 = E — симметричная и положительно определенная матрица.

Тогда, согласно замечанию 2к теореме 1.3 мы можем взять γ1 = λmin (A), γ2 = λmax (A) и положитьτ=2h22==.4λmin (A) + λmax (A)22 πh2 ( πh ))(sin()+cos22h2При этом для погрешности верна оценка||xk − x||A 6 q k ||x0 − x||A ,где q =λmin1−ξ, ξ=.1+ξλmaxТогда, если в качестве условия выхода из итерационного процесса использовать неравенство||xk − x||A 6 ε||x0 − x||A ,то число итераций, необходимых для достижения точности ε, равно'&ln 1ε.k0 (ε) =ln 1qВ нашем случае ξ достаточно мало, поэтому верна такая оценка для ln1λmin (A)ln ≈ 2ξ = 2= 2 tg2qλmax (A)πh2≈1:q2π 2 h21π2= {h = } =.4N2N 2Отсюда следует, чтоk0 (ε) =2N 2 1N2 1ln≈ln .π2ε5εК примеру, для ε = 0, 5 · 10−4 ≈ e−10 имеем:k0 (ε) = 2N 2 .Таким образом, например, если разбить отрезок на 10 частей, получив систему уравнений с числомуравнений N = 10, требуется выполнить 200 итераций, в случае разбиения отрезка на 100 частей (соответственно N = 100 уравнений) уже требуется выполнить 20000 итераций для получения решенияс заданной точностью ε.Впоследствии мы увидим, что по сравнению с другими методами метод простой итерации являетсяочень медленно сходящимся.Впоследствии мы увидим, что по сравнению с другими методами метод простой итерации являетсяочень медленно сходящимся (хотя это понятно и так, 20000 итераций — это же убить себя можно...).1.5Попеременно-треугольный итерационный методВ этом пункте мы рассмотрим еще один итерационный метод решения СЛАУ.

Этот метод работаетбыстрее метода простой итерации, но и параметры B и τ в нем выбираются не так тривиально.22Глава 1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙРассмотрим одношаговый итерационный метод:Bxk+1 − xk+ Axk = f.τВозьмем матрицу B как произведение верхнетреугольной и нижнетреугольной матриц особоговида:B = (E + ωR1 )(E + ωR2 ),(1.30)где матрицыr11R1 = ...0rij..,.r11R2 = ...0rij...rnnrnnтакие, что их сумма R1 + R2 = A, а их элементы на их диагонали равны половине соответствующихэлементов A.Теорема 1.4 (Достаточное условие сходимости ПТИМ). Пусть A — симметрическая положительноτ(просто согласование ωопределенная матрица, а матрица B задается формулой (1.30), где ω >4с τ ).

Тогда соответствующий попеременно-треугольный итерационный метод сходится.Доказательство. Преобразуем матрицу B к виду, показывающему выполнение достаточного условиясходимости. Раскроем скобки в представлении (1.30)B = (E + ωR1 )(E + ωR2 ) = E + ω(R1 + R2 ) + ω 2 R1 R2 == {так как R1 + R2 = A} = E + ωA + ω 2 R1 R2 .Заметим, что в силу симметричности матрицы A, матрицы R1 и R2 связаны следующим образом:R1 = R2T . Вычтем и добавим ωA :B = E − ωA + ω 2 R1 R2 + 2ωA = (E − ωR1 )(E − ωR2 ) + 2ωA.Покажем, что выполняется достаточное условие сходимости из теоремы 1.1. Для этого распишемтакое скалярное произведение:hBx, xi = h(E − ωR1 )(E − ωR2 )x, xi + 2ω hAx, xi .Перенесем скобку (E − ωR1 ) в правую часть скалярного произведения, а потом воспользуемся тем,что (E − ωR1 )∗ = E − ωR1T = E − ωR2 , получим:hBx, xi = h(E − ωR2 )x, (E − ωR2 )xi + 2ω hAx, xi = ||(E − ωR2 )x||2 + 2ω hAx, xi .В силу неотрицательности нормы hBx, xi > 2ω hAx, xi , что равносильно B > 2ωA, а, так как вττусловии теоремы мы взяли ω > , то выполняется достаточное условие сходимости: B > A.

Теорема42доказана.Теорема 1.5. Пусть матрица A — симметрическая положительно определенная, и пусть существуют такие константы δ > 0 и ∆ > 0, чтоA > δE,∆A > R1 R24(R1 и R2 — такие же, как в теореме 1.4).1.5. ПОПЕРЕМЕННО-ТРЕУГОЛЬНЫЙ ИТЕРАЦИОННЫЙ МЕТОД23Тогда ПТИМ сходится при любом начальном приближении со скоростью геометрической прогрессии,причем при значениях параметров√√√δ∆δδ∆2 τ=√ , γ2 =, где γ1 =·√;γ1 + γ224∆+ δ2 ω=√ .∆δ√1− ξδk+1k√ , ξ= .скорость сходимости наилучшая: ||x− x||A 6 q||x − x||A , где q =∆1+3 ξδДоказательство.

(1) Для корректности последующих формул сначала убедимся, что6 1.∆∆Из условий теоремы, так как A > δE иA > R1 R2 , следует выполнение неравенств:4δ||x||2 = δ hx, xi 6 hAx, xi ,hR1 R2 x, xi 6∆hAx, xi .4(1.31)Левую часть второго неравенства можно переписать в виде:hR1 R2 x, xi = hR2 x, R2 xi = ||R2 x||2 .(1.32)Из (1.31) очевидно следует, что2δ||x||2 6 hAx, xi =hAx, xi.hAx, xiКроме того, в силу представления матрицы AhAx, xi = hR1 x, xi + hR2 x, xi = hR2 x, xi + x, R1T x = 2 hR2 x, xi ,поэтому22hAx, xi4 hR2 x, xi4||R2 x||2 · ||x||2=6 {| hu, vi | 6 ||u|| · ||v||} 6.hAx, xihAx, xihAx, xiРаспишем это с помощью (1.31) и (1.32):4||R2 x||2 · ||x||24∆ hAx, xi ||x||26= ∆||x||2 .hAx, xi4 hAx, xiВ итоге получаем, что δ||x||2 6 ∆||x||2 для любого x 6= 0, или, что то же самое,δ 6 ∆ =⇒ ξ =δ6 1.∆(2) Теперь фиксируем некоторое ω и посмотрим, что происходит. Из доказательства теоремы 1.4следует, что B > 2ωA , откуда1A6B.2ω1Обозначимнекоторой константой γ2 , и перейдем к доказательству симметричного неравенства2ωдля γ1 .Преобразуем условия нашей теоремы:( E 6 1 A;A > δE;δ=⇒∆∆A > R1 R2 .RRA.1 2 64424Глава 1.

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙИспользовав эти неравенства в очевидном (хотя и ранее доказанном) равенствеB = E + ωA + ω 2 R1 R2 ,получим, что1∆A + ωA + ω 2 A.δ4Отсюда легко получается выражение для A :−1ω2 ∆1B.+ω+A>δ4−11ω2 ∆Обозначив γ1 =, получим, что выполняется условие теоремы 1.3, то есть+ω+δ4B6γ1 B 6 A 6 γ2 B.Кроме того, мы можем выбирать различные γ1 и γ2 , варьируя параметр ω.Теперь воспользуемся теоремой 1.3, и получим:||xk − x||A 6 q||xk−1 − x||A ,1−γ1γ2γ1γ22.

Здесь γ1 и γ2 (а, значит, и q ) неявно зависят от ω.1++1При уменьшении q скорость сходимости возрастает. Выберем ω так, чтобы q было минимально.γ2γ2 (ω)Очевидно, для этого надо минимизировать отношение> 1, и получим для. Обозначим g =γ1γ1 (ω)него такую формулу:1∆+ ω + ω2δ4 = 1 + ω∆ + 1 .g=2ω282ωδЧтобы найти экстремум, возьмем производную от g по ω :где q ==1−γ2γ1g0 =1∆.−82δω 22(заметим, что вторая произПриравняв производную к нулю, получим точку минимума ω = √δ∆водная будет больше нуля). Теперь найдем значения γ1 и γ2 в этой точке.√√11δδ∆√ ;= 2=·√ γ1 = 12ω2 ∆ √2∆+ δδ + δ∆δ +ω+ 4ω= √2δ∆√ γ = 1 = δ∆ .22ω4Воспользовавшись найденными значениями γ1 и γ2 , подсчитаем q :√γ2 − γ1q==γ2 + γ1δ∆4√δ∆4√−+δ2√δ2··√√√ δ∆∆+ δ√√√ δ∆∆+ δ=q√ √√ √√√ √√δ1−∆ δ∆ + δ δ∆ − 2 δ δ∆∆− δ∆√ √√ √√ =q .=√ √=√δ∆ δ∆ + δ δ∆ + 2 δ δ∆∆+3 δ1+3 ∆Итак, мы получили, что наибольшая скорость сходимости достигается при параметрах, указанных вусловии теоремы. Это, в общем-то, и требовалось доказать.1.6.

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

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