Численные методы. Соснин (2005) (1160462), страница 8
Текст из файла (страница 8)
.(2.5)По этой последовательности построим числовую последовательность {Λk1 } по следующему правилу: k+1 k x,xkΛ1 =.khx , xk iПусть собственные числа занумерованы так, что первым стоит максимальное по модулю — искомое:|λ1 | > |λ2 | > |λ3 | > . . . > |λn |.40Глава 2. ЗАДАЧИ НА СОБСТВЕННЫЕ ЗНАЧЕНИЯПримечание. Обратите внимание, что максимальное по модулю собственное значение единственно — мы будем этим пользоваться.Покажем, что в этом случае последовательность {Λk1 } будет сходиться к λ1 .Так как матрица A симметрическая, то для нее существует ортонормированный базис {ξi } изсобственных векторов. Разложим начальное приближение x0 по этому базису:x0 =nXαi ξi .(2.6)i=1Из (2.5) получаем выражение для xk через x0 :xk = Axk−1 = .
. . = Ak x0 .Используя разложение x0 по базису, запишем следующую оценку на xk :xk = AknXi=1αi ξi = Ak−1nXi=1αi Aξi = Ak−1nXαi λi ξi = . . . =i=1В силу того, что |λ2 | > |λi |, где i = 3, n, получим, чтоnXαi λki ξi = α1 λk1 ξ1 +i=1nXnXαi λki ξii=2αi λki ξi = O(|λ2 |k ). Подсчитаем дваi=2скалярных произведения для нахождения Λk1 . k kx ,x= α1 λk1 ξ1 + O(|λ2 |k ), α1 λk1 ξ1 + O(|λ2 |k ) k+1 k x,x= α1 λk+1ξ1 + O(|λ2 |k+1 ), α1 λk1 ξ1 + O(|λ2 |k )1kk= α12 λ2k1 + O(|λ1 | · |λ2 | );= α12 λ2k+1+ O(|λ1 |k+1 · |λ2 |k ).1Зная скалярные произведения, вычислим члены последовательности Λk1 : k2 2k+1α1 λ11 + O λλ12 2 2k+1k+1kα λ+ O(|λ1 |· |λ2 | ) = λ1 1 + O=Λk1 = 1 21 2kα1 λ1 + O(|λ1 |k · |λ2 |k ) k22kα1 λ1 1 + O λλ12 k !! λ2 −→ λ1 λ1 при k → ∞.То есть видно, что последовательность Λk1 сходится к λ1 — искомому максимальному собственномузначению.
Определим, к чему же сходится последовательность xk . Для этого рассмотрим k !λ xkα1 λk1 ξ1 + O(|λ2 |k )α1 λk1 ξ1 + O(|λ2 |k ) = ±ξ1 + O 2 p==k||x ||λ1 khxk , xk i|α1 ||λ1 |k 1 + O λλ12 Откуда видно, что xk сходится к собственному вектору ξ1 по направлению (чем больше k, темkближе ||xxk || по направлению к ξ1 ).Примечание. В разложении (2.6) в общем случае коэффициент α1 может быть равен нулю, иитерационный процесс может не сходиться. Для устранения неопределенности обычно прогоняюталгоритм для нескольких случайно выбранных начальных приближений.Примеры2.3. МЕТОД ОБРАТНОЙ ИТЕРАЦИИ41Поиск максимального собственного значения. В общем случае максимальное собственное значение может не быть максимальным по модулю. В этом случае переходят от матрицы A к матрицеD = A + cE, где c — некоторая положительная константа.
Легко заметить, что λ(D) = λ(A) + c иλmax (D) = λmax (A) + c. Очевидно, что можно подобрать такое c, что все собственные значения D будут положительны. Теперь мы пользуемся вышеприведенным алгоритмом, находим λmax (D), а потоми λmax (A).Для поиска минимального собственного значения можно брать константу c < 0 и проводить аналогичные рассуждения.Поиск собственного значения, близкого к заданному числу Λ.λ, что|λ − Λ| = min |λi − Λ|.Это задача о поиске такогоiАналогично предыдущему примеру, переходим от матрицы A к матрице D = E −c(A−ΛE)2 , c > 0.В этом случае λ(D) = 1 − c(λ(A) − Λ)2 , и максимальное собственное значение D будет соответствоватьсобственному значению A, ближайшему к Λ.2.3Метод обратной итерацииПусть нам дана матрица A.
Обозначим соответствующие ее собственному значению λi собственныевектора как xi : Axi = λi xi . Тогда(A − λi E)xi = 0.(2.7)Задача состоит в том, чтобы найти один из собственных векторов xi . Сначала для поиска собственного значения λi необходимо решать уравнениеdet(A − λi E) = 0.Если мы нашли λi точно, то вычисление xi не составит труда.
Однако, если мы получили неточноесобственное значение λi ≈ λi , то определитель det(A − λi E) будет отличен от нуля. Так как должнавыполняться формула (2.7), то единственным подходящим xi будет xi = 0.Покажем, что даже при неточно вычисленном собственном значении можно вычислить собственныйвектор. Фиксируем произвольный вектор b и решим систему:(A − λi E)x = b.(2.8)Утверждается, что решение этой системы будет приближенно равняться искомому собственномувектору: x ≈ xi . Для решения исходной системы построим последовательность векторов по следующему правилу:(2.9)(A − λi E)xk+1 = xk , k = 0, 1, . .
. ,где x0 = b.При таком задании итерационного процесса достаточно примерно 5 итераций, чтобы с хорошейточностью определить собственный вектор xi , соответствующий собственному значению λi .Покажем, что алгоритм работает правильно. Пусть матрицаXA такова, чтоXсуществует базис {ξi }из собственных векторов этой матрицы (xi = C · ξi ).
Пусть b =βj ξj и x =αj ξj — разложенияjjфиксированного вектора b и искомого вектора x по этому базису. Подставим эти разложения в (2.8)XXαj ξj =βj ξj ,(A − λi E)Xjjj(αj λj − αj λi )ξj =Xjβj ξj ,42Глава 2. ЗАДАЧИ НА СОБСТВЕННЫЕ ЗНАЧЕНИЯX[αj (λj − λi ) − βj ]ξj = 0.jТолько коэффициенты, равные нулю, могут обратить линейную комбинацию базисных векторов внуль. Следовательно, получаем такое выражение для αj :αj =βj.λj − λ iОтсюда видно, что в разложении x по базису из собственных векторов коэффициент αi при базисном векторе ξi будет велик по сравнению с другими (если λi близко к λi ).
Это означает, что каждыйшаг итерационного процесса (2.9) приводит нас к вектору, который все больше похож на искомыйсобственный вектор ξi . Можно говорить, что итерационный процесс сходится к ξi по направлению.Глава 3Численные методы решениянелинейных уравненийПусть f (x) — некоторая непрерывная функция, заданная на отрезке [a; b]. Нашей задачей будет поисккорней уравнения f (x) = 0 на этом отрезке.Обычно это проходит в два этапа: сначала проводится локализация корней: выделение небольших отрезков, содержащих только один корень, а потом на этих отрезках проводится уточнение егозначения.3.1Методы разделения корнейКак легко можно убедиться, локализация корней даже для функции одной переменной представляетсобой достаточно трудоемкую задачу.
Одним из способов является разбиение отрезка [a; b] произвольным образом на N подотрезков [xk ; xk+1 ] :x0 = a < x1 < x2 < . . . < xN = b.Теперь мы считаем значение функции на границах этих маленьких отрезков: f (xk ) = fk . Обратимсвое внимание на те из них, для которых выполняется неравенство:fk · fk+1 < 0.(3.1)Оно означает, что значения функции на краях отрезка различны по знаку, а из непрерывности f (x)следует, что она где-то внутри обращается в ноль. Далее повторяем вышеописанную процедуру длявсех отрезков, для которых верно (3.1).Упрощенным вариантом предыдущего метода является метод бисекции. Пусть f (a) · f (b) < 0 —— середина отрезкаэто означает, что внутри [a; b] точно есть корень.
Теперь обозначим x0 = a+b2[a; b]. Если он не является корнем, то либо f (a) · f (x0 ) < 0, либо f (x0 ) · f (b) < 0. Соответственно,делим пополам [a; x0 ] или [x0 ; b] и так до достижения нужной точности — очевидно, это всегда можносделать.3.2Примеры численных методовМетод простой итерации∗Пусть x — корень уравнения f (x) = 0, лежащий на отрезке [a; b]. Зададим τ (x) — некоторуюфункцию-параметр, не обращающуюся в ноль на [a; b].
Тогда, очевидно,f (x) = 0 ⇐⇒ −τ (x)f (x) = 0 ⇐⇒ x − τ (x)f (x) = x.4344Глава 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙОбозначим S(x) = x − τ (x)f (x), тогда получим, чтоf (x) = 0 ⇐⇒ S(x) = x.(3.2)Теперь будем строить последовательность приближений к x∗ по следующему правилу:xk+1 = S(xk ),k = 0, 1, . . . ,задаваясь при этом некоторым начальным приближением x0 .Если предел последовательности {xk } существует: lim xk = x∗ , то x∗ = S(x∗ ), и, согласно (3.2),k→∞он будет являться корнем исходного уравнения. Очевидно, эта последовательность не всегда будетсходиться, а зависит это от функции S(x), которая в свою очередь определяется параметром τ (x).Из геометрических соображений (нарисовав соответствующие графики) можно сделать предположение, что условие |S 0 (x)| < 1 на некотором отрезке [c; d] внутри [a; b] будет достаточным длясуществования предела {xk }, если начальное приближение тоже взять из [c; d].
Докажем это позже,а пока рассмотрим один из вариантов данного метода — метод Ньютона.Метод Ньютона1Итак, пусть x∗ — нуль функции f (x) :f (x∗ ) = 0,(3.3)а f 0 (x) существует, непрерывна и отлична от нуля на [a; b]. Это означает, в частности, что другихнулей у f (x) на этом отрезке нет. Теперь перепишем (3.3) следующим образом:f (xk + (x∗ − xk )) = 0.Применим теперь к этому выражению формулу Лагранжа:f (xk ) + f 0 (x)(x∗ − xk ) = 0, x ∈ [a; b].Для получения формулы итерационного процесса заменим в этом равенстве x на xk , а x∗ — наx.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
