Н.И. Ионкин - Электронные лекции (2010) (1135227), страница 4
Текст из файла (страница 4)
Из того, что ≤1+ и < 1,(6)следует, что<2,т.е. − 0.5 > 0.Таким образом, по теореме Самарского, сходимость имеет место.Доказательство теоремы. Из положительной определенности матрицы11∃ 2 = ( 2 )* > 0,11∃ − 2 = ( − 2 )* > 0.Домножим обе части (3) слева на1− 2 :1 +1 − + − 2 = 0.12Обозначим1 2 = .Тогда11 +1 − + − 2 − 2 = 0.следует, чтоОценка скорости сходимости итерационных методовВыразим +124:11 +1 = − − 2 − 2 .Обозначим11 = − − 2 − 2 .Тогда +1 = .Назовем матрицу(7)матрицей перехода для.Докажем, что из того, что‖ +1 ‖ ≤ ‖ ‖,следует, что‖ +1 ‖ ≤ ‖ ‖ .Действительно,11‖ ‖2 = ( , ) = ( 2 , 2 ) = ( , ) = ‖ ‖2 .Таким образом, осталось доказать, что‖ +1 ‖ ≤ ‖ ‖.(8) , = 1, .
. . , – собственные значения матрицы . Зафиксируем , пусть – собственныйсоответствующий собственному значению :Пустьвектор, = ( ̸= 0).Заметим, что1111 2 = ( 2 − − 2 ) = 2 .Обозначим1 = − 2 .Тогда предыдущее выражение можно переписать в виде:( − ) = ,(1 − ) = , =1 − .Из условия (5) теоремы следует, что1−1 − 1+(, ) ≤ (, ) =(, ) ≤(, ).Поскольку(, ) > 0,то предыдущее неравенство влечёт1−1 − 1+≤≤.Следовательно,| | ≤ , = 1, .
. . , .Поскольку все матрицы, входящие в правую часть выражения (7), являются самосопряженными,то и матрица является самосопряженной. Следовательно, существует ортонормированныйбазис { }1 , состоящий из собственных векторов матрицы : = , = 1, . . . , .Оценка скорости сходимости итерационных методовРазложим векторпо базису25{ } :∑︁ =() .=1Тогда+1= =∑︁() =∑︁=1() .=1Пользуясь равенством Парсеваля и полученной оценкой для‖+1 2‖ =∑︁()( )2 22≤∑︁| |,имеем:()( )2 = 2 ‖ ‖2 .=1=1Мы доказали (8) и (6).Cледствие 1. Пусть * = > 0, * = > 0, ∃ 0 < 1 < 2 :1 ≤ ≤ 2 .Тогда, если=21 +2= 0 ,то‖+1 ‖ ≤ ‖ ‖ ,1 и 2 :{︃1 + 2 = 2 ,⇔2 − 1 = (1 + 2 );где=(9)1−,1+=1.2Доказательство. Найдем{︃==2,1 +21−;1+{︃1 + 2 = 2 ,⇔2 − 1 = 2;{︃1 =⇔2 =1−,1+.Таким образом, мы находимся в условиях доказанной теоремы.Cледствие 2.
Пусть * = > 0, = ,– собственные значения матрицы A, = 1, . . . , ,1 = min , 2 = max .=1,...,=1,...,Тогда итерационный метод имеет види имеет место+1 − + = -оценка‖+1 ‖ ≤ ‖ ‖,где=1−1,=1+2.Доказательство. Утверждение данного следствия вытекает из утверждения предыдущего следствия.Исследование сходимости попеременно треугольного итерационного метода§826Исследование сходимости попеременно треугольного итерационметодаРассмотрим СЛАУ: = , || ≠ 0(1)Запишем попеременно треугольный итерационный метод (ПТИМ):( + 1 )( + 2 ) > 0, > 0,+1 − + = , = 0, 1, . .
. ,0(2)задано, = 1 + 2 ,⎛0, 5110⎜ 210,522⎜1 = ⎜ ....⎝ ..12⎛0, 51112⎜ 00,522⎜2 = ⎜ ....⎝ ..00······00.....⎞— нижнетреугольная матрица,···⎟⎟⎟⎠0, 5······⎞12 ⎟⎟⎟..⎠.0, 5— верхнетреугольная матрица.....···Обозначим = ( + 1 )( + 2 ).Это обозначение согласуется с обозначением для итерационного метода общего вида, рассматриваемогов предыдущих параграфах.Теорема 1.
Пусть * = > 0, >приближении0. Тогда ПТИМ (2) сходится при любом начальном4в среднеквадратичной норме.Доказательство. Распишем: = ( + 2* )( + 2 ) = + + 2 2* 2 = ( − 2* )( − 2 ) + 2Обозначим = −2 . Тогда * = ( −2* ), * > 0,т.к.( * , ) = (, ) > 0при ̸=0, − 0, 5 > − 2 = * > 0.Таким образом, по теореме Самарского, имеет место сходимость в среднеквадратичной норме.Теорема 2(об оценке скорости сходимости ПТИМ).
Пусть ≥ ,2* 2 ≤∆.4 = * > 0,∃, ∆ > 0,т.ч.(3)Исследование сходимости попеременно треугольного итерационного методаПусть2=√ ,∆=272,1 + 2(4)где√ √( ∆)√ ,1 = √2( + ∆)√2 =∆.4(5)Тогда итерационный метод (2) решения (1) сходится и имеет место оценка‖+1 − ‖ ≤ ‖ − ‖ ,где√1− =√ ,1+3 =(6),∆(7) = ( + 2* )( + 2 ).
≤ ∆.∀ ∈ : ̸= 0Доказательство. Докажем, чтоИз условия (3) следует, чтоимеем(, ) ≥ ‖‖2 ,‖2 ‖2 = (2 , 2 ) = (2* 2 , ) ≤Поскольку = 1 + 2 , 1 = 2* ,∆(, )4то(, ) = (2* , ) + (2 , ) = 2(2 , ).Таким образом,‖‖2 ≤ (, ) =(, )24(2 , )2=.(, )(, )Из неравенства Коши-Буняковского:‖‖2 ≤Сократив на‖‖2 ,получим4‖2 ‖2 · ‖‖2∆≤ 4 ‖‖2 = ∆‖‖2(, )4 ≤ ∆.В соответствии со следствием 1 параграфа 7, подберем коэффициентывыполнялось1и2так, чтобы1 ≤ ≤ 2 .Из доказательства теоремы 1 данного параграфа ≥ 2.
Таким образом, ≤1.21,22 () =11 = + + 2 2 2* ≤ + + 2 = ( + + 2 ),4411 () = ( + + 2 )−1 .4Таким образом, из следствия 1 параграфа 7 получаем, что для ПТИМ имеет место1−()(6), где () =, () = 12 ().1+()()-оценкаМетоды решения задач на собственные значенияМинимизируем().1 () =2 ′ () = 0достигается () =Для этого минимизируем′ ′′ (0 ) > 0, томинимум и ()Поскольку28приПодставив полученное значениепри = 00(︂∆1− 242 ().1 ())︂,2 = 0 = √ .∆достигается минимумв выражения для (),1 (), 2 ()иследовательно, на(),Напомним, что число итераций, необходимое для достижения точности,0получим (5) и (7).можно вычислитьпо формуле:⎡⎤ln 1⎦.0 () = ⎣ln 1Величинаln 1называется скоростью сходимости итерационного метода.Сравним ПТИМ и метод простой итерации (ПИ) по скорости сходимости.Напомним, что метод ПИ имеет вид:+1 − + = , > 0,В реальных задачах = 0, 1, .
. . ,0– задано. = (−2 ). В соответствии с этим, оценим скорость сходимости ПТИМ:√√︀1+3 1ln =√ = Θ( ()) ⇒ 0 () = Θ()1− Теперь оценим скорость сходимости ПИ:ln1+(1 + )2 ∼1= ln= ln= ln(1 + 2) ∼= ln(1 + 2) ∼= ⇒ 0 () = Θ(2 ).1−1 − 2Таким образом, ПТИМ сходится на порядок быстрее ПИ.§9Методы решения задач на собственные значенияПусть матрицаматрицыимеет размерность × .Рассмотрим задачу на собственные значения: = , ̸= 0.
и вектор удовлетворяют (1), то называется собственным значением(оператора) , а называется собственным вектором матрицы (оператора) .Для нахождения собственных значений нужно решить уравнениеЕсли число () = | − | = 0.(1)матрицыМетоды решения задач на собственные значенияПри этом, ()– многочлен степени.При29≥5данная задача аналитически не разрешимав общем случае.Заметим, что в общем случае ∈ C,даже если ∈ R×Различают две проблемы собственных значений:1. Частичная проблема собственных значений. Требуется найти некоторое подмножествоспектра матрицы A (как правило, минимальное и максимальное по модулю собственныезначения).2. Полная проблема собственных значений. Требуется найти весь спектр матрицы A.Для простоты будем рассматривать только собственные вектора, имеющие норму1: ‖‖ = 1.Степенной метод решения частичной проблемы собственных значенийЭтот метод имеет вид+1 = , = 0, 1, . .
. ,Пусть собственные значения1 , . . . , 0(2)– задано.матрицыпронумерованы так, что|1 | ≤ |2 | ≤. . . ≤ | |.Для доказательства сходимости данного метода потребуем выполнение следующих условий:A)Существует базис{ }=1из собственных векторов : = , = 1, . . . , .⃒⃒⃒ −1 ⃒< 1. ⃒B) ⃒C)При разложении начального приближения по базисувыполненоЗапишем{ } : 0 = 1 1 + 2 2 + . . .
+ ̸= 0. : = 1 1 1 + 2 2 2 + . . . + ,(︂ )︂(︂ )︂12= 11 + 22 + . . . + .Таким образом, при → ∞ стремится по направлению к собственному вектору, отвечающемумаксимальному по модулю собственному значению.()Обозначим через +1 -ую координату вектора +1 . Тогда:()()()()+1 = 1 +11 + 2 +12 + · · · + +112 ()() ()() = 1 1 1 + 2 2 2 + · · · + Поделим()+1на()()(︂(︁)︁+1)︁+1 )︂()() (︁−1 −1−11 11+ · · · + () 1 + ()(︂=(︁)︁)︁ )︂()() (︁()−1−1 −11 11 1 + ()+ · · · + () () +1 ()+1:=Методы решения задач на собственные значения(︂(︂= + Таким образом,() − = (︁(︁−1)︁ )︁30−1)︂ )︂= (), то есть мы решили задачу нахождения максимальногопо модулю собственного значения. Сформулируем соответсвующее утверждение:Утверждение.
Пусть выполнены следующие предположения:1. (A) Матрица A имеет базис из собственных векторов2. (B)| −1|<13. (С) 0 = 1 1 + 2 2 + · · · + ,Тогда → где(по направлению) при={ }=1 ̸= 0 → ∞,где- собственный вектор, отвечающий)︁ )︁(︁(︁()+1()−1наибольшему по модулю собственному значению , а = () = + .Замечание. Условия (A) и (B) несколько ограничивают класс задач, к которым применимэтот метод, хотя он все равно остается достаточно широким.()Замечание.
Найти можно также по формуле:() =(+1 , )( , )=( , )( , ).Рассмотрим два случая:*1. Пусть = . Тогда∃ { }==1- ортонормированный базис из собственных векторовматрицы A: = , = 1, . . . , , ̸= 0( , ) = +1 = 1 +11 + 2 +12 + · · · + +112 = 1 1 1 + 2 2 2 + · · · + Найдем():2+12 2+1 + 2 2+1 + · · · + 2 (+1 , )= 1 1 2 2 2 2 2 2=( , )1 1 + 2 2 + · · · + 2 2(︂(︁)︁2 (︁)︁2+1(︁ )︁2 (︁ )︁2+1 )︂−1−112 2+1 1 + + · · · + 1(︂==(︁)︁2 (︁)︁2(︁ )︁2 (︁ )︁2 )︂−1−11122 1 + + · · · + () =(︃(︂= + Таким образом, при = *−1)︂2 )︃получили более быструю сходимость.Методы решения задач на собственные значения2.
Пусть31∃ { }==1 - базис из собственных векторов (ортонормированность не предполагается).Тогда:∑︀()(+1 , )==( , ) +1 ( , ),=1∑︀= ( , ),=1(︂2+12 =( , ) 1 +(︂22 ( , ) 1 +−1 ( ,−1 )( , )(︁−1−1 ( ,−1 )( , )(︁−1)︁)︁+ ··· +(︁1+ ··· +(︁1)︁2)︁2(1 ,1 )( , )(︁1(1 ,1 )( , )(︁1)︁2+1 )︂)︁2 )︂=)︂ )︂−1= + (︂(︂)︂ )︂−1() − = (︂(︂Метод обратных итерацийПусть матрица(m x m) такова, что∃−1 .Рассмотрим итерационный степенной методрешения частичной проблемы собственных значений:+1 = ,Домножим обе части слева на = 0, 1, . . . ,0— задан.−1 :+1 = −1 , = 0, 1, .
. . ,0— задан.Получили степенной метод для обратной матрицы. Пусть верны следующие предположения:1. (A) Матрица A имеет базис из собственных векторов2. (B)| 12 | < 13. (С)0 = 1 1 + 2 2 + · · · + ,где{ }==11 ̸= 0Тогда:−− = 1 −1 1 + 2 2 2 + · · · + (︂ )︂(︂ )︂11 1 = 1 1 + 2 2 + · · · + 2Таким образом, → 1(по направлению) при → ∞.Задача. Пусть выполнены условия (A), (B)(︁(︁и (C). Тогда метод обратных итераций позволяет)︁ )︁найти собственное значение()1 = 1 + 12, где()1 =()() .+1Методы решения задач на собственные значения()Доказательство. Выпишем выражения для32и()()+1 :()−−− ()() = 1 1 1 + 2 2 2 + · · · + ()()()+1 = 1 −−11 + 2 −−12 + · · · + −−1()12()Теперь поделимна()+1 :(︂)︁−(︁ )︁− )︂() (︁()22 2 1 + 1 () 1+ · · · + 1 () 111(︂=(︁)︁(︁ )︁−−1 )︂ =−−1()()−−1 ()22 2 + · · · + 1 () 11 11 1 + 1 () 1()1 −1 1()()+111(︂(︂= 1 + = * .()Найдем 1 :Пусть теперьматрицы A.Тогда∃ { }==112)︂ )︂()= 1- ортонормированный базис из собственных векторов−221 1−2 + 22 2−2 + · · · + 2 ( , )== 2 −2+1−2−1(+1 , )+ · · · + 2 + 22 −2−11 12(︂(︁ )︁2 (︁ )︁−2(︁ )︁2 (︁ )︁−2 )︂222 −21 11 + 1+ · · · + 111(︂=(︁ )︁2 (︁ )︁−2−1 )︂ =(︁ )︁2 (︁ )︁−2−1222 −2−11 1+ · · · + 11 + 111(︃(︂ )︂ )︃21= 1 + 2() =Таким образом, приЗадача.(︁(︁ )︁12 = *снова имеем более быструю сходимость.=)︁Пусть ∃ { }=1 - базис из собственных векторов матрицы A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
