Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 5
Текст из файла (страница 5)
Выберем любой собственный вектор ei линейногопреобразования с матрицей A , тогда( Aei , ei ) = λi > 0 .Достаточность. Расположим для определенности все характеристическиезначения матрицы A = A* в порядке убывания:λ1 ≥ λ2 ≥ K ≥ λn > 0 .Поскольку по условию леммы λi > 0 , то в ортонормированном базисе изсобственных векторов преобразования с матрицей A для любого x ≠ 0 имеемn⎛ n⎞( Ax, x) = ∑ λiξi2 > 0 , ∀{ξi } , ⎜ ∑ ξi2 > 0 ⎟ .i =1⎝ i =1⎠Поэтому, очевидно, что A > 0 .Лемма 2.- 19 -Пусть A = A* > 0 , и λ1 ≥ K ≥ λn > 0 - упорядоченный набор характеристических чиселэтой матрицы, тогда22λn x ≤ ( Ax, x) ≤ λ1 x .(82)Доказательство предлагается провести самостоятельно.Лемма 3.Если A > 0 , то всегда найдется постоянное число δ > 0 , такое что2( Ax, x) ≥ δ x , ∀x ∈ En(83)Доказательство.Если A = A* , то достаточно положить δ = λn .
В общем случае напомним, что согласно(79)( Ax, x) = ( Ax, x) > 0 ,где A = A* , поэтому согласно предыдущей лемме2( Ax, x) = ( Ax, x) ≥ λn x ,где λn > 0 - минимальное характеристическое число матрицы A = ( A + A∗ ) / 2 . Полагая,что δ = λn , приходим к требуемому неравенству (83).3.3. Достаточные условия сходимости итерационного процесса.В этом разделе мы рассмотрим стационарный итерационный процесс (65), когдаматрица B и итерационный параметр τ не зависят от индекса k , и докажемследующую теорему о достаточных условиях его сходимости.Теорема СамарскогоПусть A - самосопряженная положительно определенная матрица:A = A* , A > 0 ,(84)B−τ2A - положительно определенная матрица, τ - положительное число:τ(85)A > 0, τ > 0.2Тогда при любом выборе нулевого приближения x0 итерационный процесс, которыйопределяется рекуррентной формулой (65), сходится к решению исходной системы(62).B−Прежде, чем переходить к доказательству теоремы, обсудим более подробноглавное ее требование – положительную определенность матрицы B −требование можно переписать в виде:τ( Bx, x ) > ( Ax, x ) , ∀x ∈ En , x ≠ 0 .τ2A .
Это(86)2т. е. оно, в частности, предполагает, что матрица B является положительноопределенной. Кроме того, неравенство (86) определяет интервал, в котором можетизменяться параметр τ :- 20 2 ( Bx, x ).(87)x ≠ 0 ( Ax, x )После этих замечаний перейдем к доказательству теоремы. Выразим изсоотношения (69) x k через z k :xk = z k + xи подставим в рекуррентную формулу для итерационной последовательности (65). Врезультате получим:z −zB k +1 k + Az k = 0 .(88)0 < τ < τ 0 = infτОтличие итерационной формулы (88) от (65) заключается в том, что она являетсяоднородной.Матрица B - положительно определенная. Следовательно она невырожденная иимеет обратную B −1 .
С ее помощью рекуррентное соотношение (88) можно разрешитьотносительно z k +1 :z k +1 = z k − τ B −1 Az k = z k − τ ω k ,(89)гдеω k = B −1 Az k , так что Az k = Bω k .(90)Умножая обе части равенства (89) слева на матрицу A , получим еще однорекуррентное соотношение(91)Az k +1 = Az k − τ Aω k .Рассмотрим последовательность положительных функционалов:J k = ( Az k , z k ) .(92)Составим аналогичное выражение для J k +1 и преобразуем его с помощьюрекуррентных формул (89) и (91):J k +1 = ( Az k − τ Aω k , z k − τ ω k ) = ( Az k , z k ) − τ ( Aω k , z k ) −(93)−τ ( Az k , ω k ) + τ 2 ( Aω k , ω k ) .Из самосопряженности матрицы A и формулы (90) следует( Aω k , z k ) = ( Az k , ω k ) = ( Bω k , ω k ).В результате формула (93) принимает вид:τ ⎞⎛⎛⎞J k +1 = J k − 2τ ( Bωk , ωk ) + τ 2 ( Aωk , ωk ) = J k − 2τ ⎜ ⎜ B − A ⎟ ωk , ωk ⎟ .(94)2 ⎠⎝⎝⎠Таким образом, последовательность функционалов J k с учетом условияB−τA > 0 образует монотонно невозрастающую последовательность, ограниченную2снизу нулем(95)J k ≥ J k +1 ≥ L ≥ 0 .Поэтому она сходится.
Далее, согласно лемме 3⎛⎛τ ⎞⎞2⎜ ⎜ B − 2 A ⎟ ωk , ωk ⎟ ≥ δ ωk ,⎠⎝⎝⎠- 21 где δ > 0 - строго положительная константа. В результате, согласно (94) и (95) будемиметь⎛⎛τ ⎞⎞2J k +1 − J k = 2τ ⎜ ⎜ B − A ⎟ ω k , ω k ⎟ ≥ 2τδ ω k .(96)2 ⎠⎝⎝⎠Из этого неравенства и сходимости последовательности функционалов J k следует, чтоω k → 0 при k → ∞ . В свою очередь z k = A−1Bω k , так чтоz k ≤ A−1 ⋅ B ⋅ ω k → 0Теорема доказана.3.4.
Метод простой итерации.Такое название получил метод, при котором в качестве матрицы B выбираетсяединичная матрица: B = E , а итерационный параметр τ предполагается независящимот номера итерации k . Иными словами, метод простой итерации – это явныйстационарный метод, когда очередная итерация xk +1 вычисляется по рекуррентнойформулеx k +1 = ( E − τ A ) x k + τ f(97)Будем считать, что матрица A удовлетворяет условию теоремы Самарского,A = A* > 0 , тогда формула (87), определяющая границу интервала сходимости поитерационному параметру τ , принимает вид2 ( x, x )2.(98)τ 0 = inf=x ≠ 0 ( Ax, x )Ax, x )(supx ≠ 0 ( x, x )Пусть e1 , e2 ,K, en - ортонормированный базис собственных векторов оператора,соответствующего матрице A .
В силу положительной определенности все егособственные значения положительны. Будем считать их занумерованными в порядкеубывания:λ1 ≥ λ2 ≥ L ≥ λn > 0(99)Разложим вектор x ≠ 0 по базису собственных векторовx = ξ1e1 + ξ 2e2 + L + ξ n en ,тогда( x, x ) = ξ12 + ξ 2 2 + L + ξn 2 , ( Ax, x ) = λ1ξ12 + λ2ξ 2 2 + L + λnξn 2иAx, x )(λ1ξ12 + λ2ξ 2 2 + L + λnξ n 2sup= sup= λ1 .ξ12 + ξ 2 2 + L + ξ n 2x ≠ 0 ( x, x )x≠0В результате из формулы (87) следует, что метод простой итерации сходится прилюбом τ , принадлежащем интервалу20 <τ <τ0 = .(100)λ1Дальнейшее исследование метода простой итерации построим на конкретноманализе рекуррентной формулы (97). Введем матрицу оператора перехода- 22 S = E −τ A, S = S*(101)и перепишем формулу (97) в видеx k +1 = Sx k + τ f .(102)При этом погрешность z k = x − x k будет удовлетворять аналогичному рекуррентномусоотношению, только однородному(103)z k +1 = Sz k .Докажем две леммы, которые позволяют более полно исследовать условия сходимостиметода простой итерации.Лемма 1Пусть оператор, который порождает матрица A , имеет собственный вектор ei ссобственным значением λi , тогда оператор перехода, который порождаетсяматрицей S (101), также имеет собственный вектор ei , но с собственнымзначениемµi (τ ) = 1 − τλi .(104)Доказательство элементарно.
Оно проводится прямой проверкойSei = ( E − τ A ) ei = (1 − τλi ) ei = µieiПри самосопряженной матрице A матрица S также является самосопряженной(101). Следовательно, ее норма определяется наибольшим по модулю собственнымзначением µi (τ ) (104):S = max µi (τ ) .(105)1≤i ≤ nЛемма 2Для того, чтобы метод простой итерации сходился к решению системы (62) прилюбом выборе начального приближения, необходимо и достаточно, чтобы всесобственные значения оператора перехода S были по модулю меньше единицы:µi (τ ) < 1 , 1 ≤ i ≤ n(106)Достаточность. Условие (106) означает, что норма матрицы S , согласно (105),будет меньше единицы: S < 1 .
В результате получаемkz k +1 ≤ S ⋅ z k ≤ L ≤ S ⋅ z 0 → 0 , при k → ∞ .(107)Необходимость. Допустим, что среди собственных значений µi (104) нашлосьхотя бы одно µ j , которое не удовлетворяет условию леммы (106), т. е.µ j ≥ 1.Выберем нулевой член итерационной последовательности в виде x0 = x + e j , где xрешение системы (62), тогда нулевой член последовательности погрешностейсовпадет с собственным вектором e j оператора перехода S : z 0 = e j .
В результатерекуррентная формула для следующих членов последовательности погрешностейпримет вид:zk = S ke j = µ jke j , zk = µ jk≥ 1.- 23 т. е. z k → 0 . Необходимость выполнения неравенства (106) для всех собственныхзначений µi для сходимости метода простой итерации доказана.Лемма 2 определяет программу дальнейшего исследования сходимости методапростой итерации: нужно установить диапазон изменения параметра τ при которомвсе собственные значения удовлетворяют неравенству (106).
Это легко сделать. Нарис. 1 приведены графики убывающих линейных функций µi (τ ) (104). Все онивыходят из одной точки τ = 0 , µ = 1 и идут вниз из-за отрицательных коэффициентовпри τ , причем быстрее всех убывает функция µ1 (τ ) . Когда она принимает значение( −1) , условие (106) для нее перестает выполняться:µ1 (τ ) = 1 − τλ1 = −1, при τ = τ 0 = 2 / λ1 .Найденное значение τ 0 является границей интервала сходимости метода простойитерации0 < τ < τ 0 = 2 / λ1 .(108)Это неравенство нам уже известно. Оно было получено ранее из теоремыСамарского как достаточное условие сходимости.
Дополнительный анализ на основелеммы 2 позволяет уточнить результат. Теперь мы установили, что принадлежностьитерационного параметра τ интервалу (108) является необходимым и достаточнымусловием сходимости метода простой итерации.Перейдем к исследованию скорости сходимости метода. Оценка погрешности(107) показывает, что она убывает по закону геометрической прогрессии сознаменателемq (τ ) = S = max µ i (τ ) .1≤i ≤ nРассмотрим рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
