Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 6
Текст из файла (страница 6)
2, который поможет нам провести анализ этой формулы. Онаналогичен рис.1, только на нем приведены графики не функций µi (τ ) , а их модулей.При малых τ все собственные значения µi (τ ) (104) положительны, причемнаибольшим из них является µ n (τ ) , которое убывает с ростом τ с наименьшейскоростью. Однако с переходом через точку τ 0 / 2 собственное значение µ1 (τ ) , меняязнак, становится отрицательным. В результате теперь его модуль с увеличением τ неубывает, а растет и при τ → τ 0 приближается к предельному значению – к единице.Найдем на отрезке [ 12 τ 0 ,τ 0 ] точку τ * , в которой убывающая функция µ n (τ )сравниваетсяуравнениемсвозрастающейфункциейµ1 (τ ) = − µ1 (τ ) .Онаопределяетсяµ n (τ ) = 1 − τλn = − µ1 (τ ) = τλ1 − 1 ,которое даетτ* =В результате получаем:2<τ .λ1 + λn 0(109)- 24 ⎧⎪ µ n (τ ) , 0 < τ ≤ τ *S = max µi (τ ) = ⎨(110)1≤i ≤ n,.−µττ≤τ<τ⎪⎩ 1 ( ) *0Свое наименьшее значение норма матрицы S достигает при τ = τ * :λ − λ M −1min S = 1 − τ *λn = 1 n = A.(111)λ1 + λn M A + 1Формула (111) показывает, что для плохо обусловленной матрицы даже приоптимальном выборе итерационного параметра τ = τ * норма матрицы S близка кединице, так что сходимость метода простой итерации в этом случае оказываетсямедленной.В заключение заметим, что формула (108), определяющая границу интерваласходимости τ 0 , и формула (109) для оптимального значения итерационного параметраτ * представляют прежде всего теоретический интерес.
Обычно при решении СЛАУнаибольшее и наименьшее характеристические числа матрицы A неизвестны, так чтоподсчитать величины τ 0 и τ * заранее невозможно. В результате итерационныйпараметр τ нередко приходится подбирать прямо в процессе вычислений методомпроб и ошибок.Задача 2.Рассмотреть систему двух уравнений с двумя неизвестными⎧ x1 + x2 = 0,(112)⎨⎩ x1 + 2 x2 = 1.и построить для нее приближенное решение с помощью метода простой итерации.Выпишем сразу решение системы (112)x1 = −1, x2 = 1 ,(113)чтобы потом иметь возможность сравнивать его с членами итерационнойпоследовательности.Перейдем к решению системы методом простой итерации. Матрица системыимеет вид⎡1 1 ⎤A=⎢⎥.12⎣⎦Она самосопряженная и положительно определенная, поскольку2( Ax, x ) = ( x1 + x2 ) x1 + ( x1 + 2 x2 ) x2 = ( x1 + x2 ) + x2 2 > 0 .Составим характеристическое уравнение для матрицы A и найдем его корни:1− λ1= λ 2 − 3λ + 1 = 0 ,12−λ3+ 53− 5≈ 2.618 , λ2 =≈ 0.38222С их помощью можно определить границу интервала сходимости τ 0 и оптимальноезначение итерационного параметра τ * :λ1 =- 25 2≈ 0.745 .λ1λ1 + λ2Для построения итерационной последовательности выберем какое-нибудьзначение итерационного параметра на интервале сходимости, например, τ = 1/ 2 .
Вэтом случае рекуррентная формула для членов итерационной последовательности(102) принимает вид:⎡ 1/ 2 −1/ 2 ⎤1x k +1 = Sx k + f , где S = ⎢0 ⎥⎦2⎣ −1/ 2Возьмем простейшее начальное приближение x0 = 0 и выпишем несколько первыхчленов итерационной последовательности x k , подсчитывая для каждого из нихневязку ψ k (71). В результате получим:1⎧ 1⎫⎧1 ⎫x1 = ⎨0, ⎬ , ψ1 = ⎨ ,0 ⎬ , ψ 1 = ,2⎩ 2⎭⎩2 ⎭1⎧ 1 1⎫⎧1 1 ⎫x 2 = ⎨− , ⎬ , ψ 2 = ⎨ , − ⎬ , ψ 2 =,2 2⎩ 4 2⎭⎩4 4⎭5⎧ 3 5⎫⎧1 1⎫x3 = ⎨− , ⎬ , ψ 3 = ⎨ , − ⎬ , ψ 3 =,8⎩ 8 8⎭⎩4 8⎭τ0 =2≈ 0.764 , τ * =10⎧ 1 11 ⎫⎧ 3 1⎫x 4 = ⎨− , ⎬ , ψ 4 = ⎨ , − ⎬ , ψ 4 =.16⎩ 2 16 ⎭⎩16 8 ⎭Норма невязок, хотя и медленно, но убывает, что говорит о сходимости процесса.
Этоже видно из сравнения членов итерационной последовательности x k с решениемсистемы (113). Медленная сходимость связана с плохой обусловленностью матрицыA:MA =λ1≈ 6.854 .λ23.5. Неявные итерационные методы. Метод Зейделя.Вернемся к общей записи итерационного стационарного процесса в каноническойформе (65).Рассмотрим произвольную квадратную матрицу:⎡ a11 a12 K a1m ⎤⎢aa22 K a2 m ⎥21⎢⎥.A=⎢K K K K ⎥⎢⎥⎣am1 am 2 K amm ⎦Разложим её на сумму трех матрицA = D + TH + TB ,(114)где D - диагональная часть матрицы A , которая содержит элементы aii , стоящие наглавной диагонали:- 26 ⎧0, i ≠ jDij = a ij δ ij = ⎨,=a,ijii⎩TН - нижняя треугольная матрица⎧a , i > j,(Т H )ij = ⎨ ij⎩0, i ≤ jTB - верхняя треугольная матрица.⎧0, i ≥ j(Т B )ij = ⎨a , i < j .⎩ ijВ классическом методе Зейделя, записанном в канонической форме, полагаютB = D + TH ,(115)τ = 1.В результате формула (65) принимает вид:( D + TH ) ( x k +1 − x k ) + Axk = f ,или(116)( D + TH ) x k +1 + TB xk = f .Перейдем от векторной формы записи рекуррентной формулы (116) к построчной:a11 x1k +1 + a12 x2k + a13 x3k + L + a1n xnk= f1a21 x1k +1 + a22 x2k +1 + a23 x3k + L + a2 n xnk= f2(117)MMan1 x1k +1 + an 2 x2k +1 + an 3 x3k +1 + L + ann xnk +1 = f n .Уравнения (117) позволяют последовательно рассчитать компоненты вектора ( k + 1) ой итерации подобно тому, как это делалось во время обратного хода в методе Гаусса:i −1n⎤1 ⎡xik +1 = ⎢ f i − ∑ aij x kj +1 − ∑ aij x kj ⎥ , i = 1,K, n .(118)aii ⎣j =1j =i +1⎦Формула (118) предполагает, что aii ≠ 0 , 1 ≤ i ≤ n .
Если матрица A удовлетворяетусловиям теоремы Самарского (84): A = A* > 0 , то, согласно неравенству (81), все еедиагональные элементы должны быть строго положительными и, тем самым, не могутобращаться в ноль.Алгоритм в методе Зейделя прост и удобен для вычислений. Он не требуетникаких действий с матрицей A . Ранее вычисленные на текущей итерациикомпоненты x kj +1 ( j < i ) сразу же участвуют в расчетах наряду с компонентамиx kj ( j > i ) и, таким образом, не требуют дополнительного резерва памяти, чтосущественно при решении больших систем.Сходимость метода Зейделя в случае, когда матрица A удовлетворяет условиютеоремы Самарского, т.е.
является самосопряженной и положительно определенной,будет доказана в следующем разделе. К этому утверждению добавим бездоказательства еще один результат: метод Зейделя сходится для любой системы (62), вкоторой матрица A обладает свойством диагонального преобладания.- 27 -Задача 3.Рассмотреть систему (112) (см. задачу 2) и построить для нее приближенноерешение с помощью метода Зейделя.В рассматриваемом случае рекуррентные формулы (118) для построения ( k + 1) ой итерации по k -ой итерации принимают вид:x1k +1 = − x2k(119)1x2k +1 = (1 − x1k +1 ) .2Принимая, как и при решении задачи 2, за начальное приближение нулевой вектор,подсчитаем по формулам (119) несколько первых итераций, сопровождая этот процессподсчетом невязки:1⎧ 1⎫⎧1 ⎫x1 = ⎨0, ⎬ , ψ1 = ⎨ ,0 ⎬ , ψ 1 = ,2⎩2 ⎭⎩ 2⎭1⎧ 1 3⎫⎧1 ⎫x 2 = ⎨− , ⎬ , ψ 2 = ⎨ ,0 ⎬ , ψ 2 = ,4⎩4 ⎭⎩ 2 4⎭1⎧ 3 7⎫⎧1 ⎫x3 = ⎨− , ⎬ , ψ 3 = ⎨ ,0 ⎬ , ψ 3 = .8⎩8 ⎭⎩ 4 8⎭Обсудим полученные результаты.
Начнем с невязки. Ее вторая компонента всевремя остается равной нулю, поскольку второе уравнение системы на каждойитерации выполняется, как видно из (119), точно. Первые компоненты невязки инорма убывают по закону геометрической прогрессии с знаменателем 1 / 2 , т.е. гораздобыстрее, чем в методе простой итерации. Хорошая сходимость процесса видна такжеиз прямого сравнения членов итерационной последовательности x k с точнымрешением системы x = {−1,1} .3.6.
Метод верхней релаксацииМодифицируем метод Зейделя. С этой целью введем параметр ω и запишемрекуррентное соотношение (65) в виде(x − x )(120)( D + ωTH ) k +1 k + Ax k = f .ωВ данном случаеB = D + ωTH , τ = ω > 0 .(121)При ω = 1 мы возвращаемся к методу Зейделя.Соотношению (120) можно придать вид⎛1⎞(122)⎜ D + TH ⎟ ( x k +1 − x k ) + Ax k = f .⎝ω⎠Такая форма записи показывает, что параметр ω влияет на диагональ матрицы B .Для построения алгоритма вычисления очередной итерации нужно разделить влевой части рекуррентной формулы (122) члены, содержащие x k и x k +1 , и придать ейформу, аналогичную (116):- 28 ⎡⎛1⎞⎤⎛1⎞(123)⎜ D + TH ⎟ x k +1 + ⎢⎜ 1 − ⎟ D + TB ⎥ x k = f .⎝ω⎠⎣⎝ ω ⎠⎦Если перейти от векторной записи к записи типа (117) в виде отдельных уравнений, томожно получить для компонент xik +1 очередной итерации формулы, структурнопохожие на (118):i −1n⎞ω⎛k +1kk +1xi = xi + ⎜ fi − ∑ aij x j − ∑ aij x kj ⎟ , i = 1,K, n .(124)aii ⎝j =1j =i⎠Исследуем условия сходимости метода верхней релаксации при дополнительномпредположении, что матрица A удовлетворяет условиям теоремы Самарского (84).Самосопряженность матрицы A означает, что TH* = TB , TB* = TH .
Отсюда следует(TH x, x ) = (TH* x, x ) = (TB x, x ) .Составим для рассматриваемого случая матрицу B −(125)τA . Согласно (121)2τωω⎛ ω⎞B − A = ( D + ωTH ) − ( D + TH + TB ) = ⎜1 − ⎟ D + (TH − TB ) .(126)222⎠2⎝Запишем условие ее положительной определенности⎛⎛τ ⎞ ⎞ ⎛ ω⎞−BA ⎟ x, x ⎟ = ⎜1 − ⎟ ( Dx, x ) > 0 .(127)⎜⎜2 ⎠2⎠⎝⎝⎠ ⎝Второе слагаемое в выражении (126) не дает вклада в квадратичную форму (127) всилу соотношения (125).Матрица A является, по предположению, положительно определенной.Следовательно, все ее диагональные элементы строго положительны: aii > 0 , 1 ≤ i ≤ n .Это означает положительную определенность матрицы D : ( Dx, x ) > 0 .
В результатезнак выражения (127) определяется знаком первого множителя, так что достаточноеусловие для сходимости итерационной последовательности метода верхнейрелаксации принимает вид:0 <ω < 2(128)Метод Зейделя, соответствующий случаю ω = 1, удовлетворяет этому условию.Можно поставить вопрос об оптимальном выборе параметра ω = ω* , при которомметод сходится быстрее всего. Теоретическое исследование, на котором мы не будемостанавливаться, показывает, что такое значение существует и может быть выраженочерез наибольшее и наименьшее собственные значение матрицы A .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
