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

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

Матрицами отражения называются матрицы вида V() = V_ = E - 2^T. Умножение на матрицу V_ называется преобразованием Хаусхолдера (или отражением); это преобразование можно интерпретировать как ортогональное отражение вектора относительно гиперплоскости, проходящей через начало координат и имеющей нормальный вектор .

Утверждение 12.1. Матрица отражения является самосопряженной.

Утверждение 12.2. Матрица отражения является унитарной.

Утверждение 12.3. Матрица отражения V_ имеет собственное значение (-1) кратности 1, которому отвечает собственный вектор ; и собственное значение 1 кратности n-1, которому отвечает собственное подпространство, ортогональное к .

Утверждение 12.4. Пусть е - произвольный единичный вектор. Тогда для любого вектора y найдется единичный вектор , такой, что V_y = ||y|| e.

Матрица А=[a_ij] называется верхней почти треугольной (или верхней Гессенберговской), если a_ij=0 при i>j+1.

Теорема 12.5. Всякая невырожденная матрица А может быть представлена в виде A = QRQ^T, где матрица Q - унитарная, а матрица R - верхняя почти треугольная.

Алгоритм. Обозначим a₁ = (a₂₁,...,a_n1). Согласно утв. 12.4., найдется вектор x₁, такой, что V(x₁) a₁ = || a₁|| e₁, где е₁=(1,0,...,0). Положим

.

Умножим матрицу А на U₁ сначала слева, а потом справа: A₁ = U₁A U₁. В первом столбце матрицы А все элементы, начиная с 3-его, будут равны 0.

Аналогичный процесс повторяется для произвольного k=2,..,n-2.

13. Понятие о QR-алгоритме решения полной проблемы собственных значений. Сохранение верхней почти-треугольной формы при QR-алгоритме.

См. [3, стр. 486 (11.6)], [6], стр.123.

QR-разложением называется представление матрицы А в виде A=QR, где матрица Q - ортогональная, а матрица R - верхнетреугольная с положительными элементами на главной диагонали.

Утверждение 13.1. Для любой невырожденной вещественной матрицы А ее QR-разложение существует и единственно.

QR-алгоритм позволяет находить все собственные значения невырожденной матрицы A. Будем строить последовательность {A_k} матриц по следующим правилам: A₁=A, а каждая последующая матрица A_k+1 получается из A_k следующим образом:

1) строим QR-разложение матрицы A_k: A_k=Q_kR_k,

2) вычисляем матрицу A_k+1 как произведение матриц Q_k и R_k в обратном порядке: A_k+1= R_kQ_k.

Теорема 13.2.Пусть собственные значения матрицы А таковы, что

|⁽¹⁾| > |⁽²⁾| > ... > |⁽ⁿ⁾|.

Тогда диагональные элементы матрицы A_k сходятся к собственным значениям матрицы А (порядок собственных значений может и нарушаться).

Утверждение 13.3. Если матрица А - верхняя почти треугольная, то все матрицы A_k , получаемые в QR-алгоритме - почти треугольные.

FAQ: Численные Методы, часть IV

Нелинейные уравнения

14. Метод простой итерации решения нелинейных уравнений. Сходимость метода.

См. [8, стр. 190]

Пусть задана функция f(x) действительного переменного. Требуется найти нули этой функции или корни уравнения

f(x) = 0. (14.1)

Метод простой итерации состоит в том, что уравнение (1) заменяется эквивалентным уравнением

x = s(x), (14.2)

задается начальное приближение x₀ и итерации проводятся по правилу

x_k+1=s(x_k). (14.3)

Для сходимости процесса (14.3) большое значение имеет выбор функции s(x). Эту функцию можно задавать различными способами, ооднако обычно она берется в виде

s(x) = x+(x)f(x), (14.4)

причем функция (x) знакопостоянна на отрезке, где отыскивается корень. В частности, если (x)==const, то получим метод релаксации.

Теорема 14.1. Если функция s(x) на отрезке U_r(a) удовлетворяет условию Липшица с константой q(0;1), причем

|s(a) - a|  (1 - q)r, (14.5)

то уравнение (14.2) имеет на этом отрезке единственное решение x_* , и метод простой итерации (14.3) сходится к x_* при любом начальном приближении x₀ U_r(a). Для погрешности справедлива оценка

|x_k - x_*|  q^k| x₀ - x_*|. (14.6)

Утверждение 14.2. Если на всем отрезке U_r(a) выполнено условие

|s’(x)| q<1

и начальное приближение выбирается из этого отрезка, то решение (14.2) на этом отрезке единственно, метод (14.3) сходится и справедлива оценка (14.6).

15. Метод Ньютона решения нелинейных уравнений и систем нелинейных уравнений. Метод секущих.

См. [8, стр. 199].

В методе Ньютона (или касательных) итерации проводятся по следующему правилу:

. (15.1)

Метод секущих получается из метода Ньютона заменой производной на разделенную разность, вычисляемую по значениям x_k и x_k-1. В этом методе необходимо задать два начальных приближения.

Пусть F=(f₁,...,f_m) - система функций от m переменных. Будем решать нелинейную систему уравнений вида

F(x) = 0 (15.2).

Метод Ньютона для системы (15.2) можно записать в виде:

, (15.3)

где .

16. Сходимость метода Ньютона для решения нелинейных уравнений.

Утверждение 16.1. Пусть f’(x)0 в некоторой окрестности корня U_r(x_*), а вторая производная f(x) непрерывна в этой окрестности. Если

и , (16.1)

причем

, (16.2)

то метод Ньютона сходится, причем для погрешности справедлива оценка

|x_k+1 - x_*|  q^2k+1| x₀ - x_*|. (16.3)

FAQ: Численные Методы, часть V

Интерполирование и приближение функций

17. Постановка задачи интерполирования. Интерполяционная формула Лагранжа. Погрешность формулы.

См. [8, стр. 127]

Задача интерполирования состоит в том, чтобы по значениям функции f(x) в некоторых точках отрезка восстановить ее значения в остальных точках этого отрезка.

Иногда возникает необходимость аппроксимации данной функции другими функциям, которые легче вычислить. В частности, рассматривается задача о наилучшем приближении в нормированном пространстве Н, когда заданную функцию f требуется заменить линейной комбинацией  заданных элементов из Н так, чтобы отклонение ||f - || было минимальным.

Пусть на отрезке [a; b] заданы узлы интерполирования x_k (k=0,1...,n), в которых известны значения f_k=f(x_k). Задача интерполирования алгебраическими многочленами состоит в том, чтобы построить интерполяционный многочлен n-й степени

L_n(x)=a₀+a₁x+...+a_nxⁿ, (17.1)

значения которого в точках x_k совпадают со значениями f_k функции f(x) в этих точках.

Интерполяционный многочлен в форме Лагранжа имеет вид

, (17.2)

где . (17.3)

Пусть (x) = (x - x₀) (x - x₁)... (x - x_n). Тогда выражение (17.3) для c_k можно записать в виде

Разность r_n(x) = f(x) - L_n(x) называется погрешностью интерполирования или остаточным членом интерполяционной формулы.

Утверждение 17.1. Предположим, что функция f(x) имеет на [a;b] непрерывные производные до (n+1)-го порядка включительно. Тогда для погрешности интерполирования r_n справедлива следующая оценка:

(17.4),

где .

18. Разделенные разности. Интерполяционная формула Ньютона.

Разделенными разностями первого порядка называются отношения вида

(18.1).

Пусть известны две разделенные разности k-ого порядка f(x₀,x₁,...,x_k) и f(x₁,x₂,...,x_k+1). Разделенная разность (k+1)-ого порядка определяется как

(18.2)

Интерполяционная формула Ньютона является разностным аналогом формулы Тейлора:

P_n(x) = f(x₀) + (x - x₀) f(x₀,x₁) + (x - x₀)( x - x₁) f(x₀,x₁,x₂) + ...

+ (x - x₀) (x - x₁)...(x - x_n-1) f(x₀,x₁,...,x_n). (18.3)

19. Понятие об интерполировании с кратными узлами. Построение полинома H₃(x). Оценка погрешности H₃(x).

См. [8, стр. 214].

Более общая постановка задачи интерполирования состоит в следующем. В узлах x_k[a;b] (k=0,1,...,m), среди которых нет совпадающих узлов, заданы значения функции f(x_k) и ее производных f⁽ⁱ⁾(x_k) до порядка (N_k - 1) включительно. Всего известно N=N₀+ N₁+...+ N_n величин. Требуется построить алгебраический многочлен H_n(x) степени n=N-1, для которого

(k = 0...n, i = 0...N_k-1). (19.1)

Многочлен H_n(x), удовлетворяю называется многочленом Эрмита для функции f(x).

Утверждение 19.1. Многочлен Эрмита существует и единственен.

Построим полином третьей степени H₃(x) по значениям функции f(x) в трех точках x₀ , x₁ , x₂ и по значению производной в точке x₁. Будем искать этот многочлен в виде

H₃(x)=c₀(x)f₀+c₁(x)f₁+ c₂(x)f₂+b(x)f’₁, (19.2)

где c₀(x),c₁(x),c₂(x),b(x)РHП - многочлены третьей степени.

Для того, чтобы H₃(x) был многочленом Эрмита, достаточно потребовать

с₀(x₀)=1, с₀(x₁)=0, с₀(x₂)=0, с’₀(x₁)=0 (19.3)

с₁(x₀)=0, с₁(x₁)=1, с₁(x₂)=0, с’₁(x₁)=0 (19.4)

с₂(x₀)=0, с₂(x₁)=0, с₂(x₂)=1, с’₂(x₁)=0 (19.5)

b(x₀)=0, b(x₁)=0, b(x₂)=0, b’(x₁)=1 (19.6)

Из условий (19.3-6) можно получить следующие выражения для многочленов c₀(x),c₁(x),c₂(x),b(x):

(19.7)

(19.8)

(19.9)

(19.10)

Утверждение 19.2. Пусть (x) = (x - x₀)(x - x₁)²(x - x₂). Погрешность приближения функции f полиномом H₃(x) удовлетворяет следующей оценке:

(19.11)

где . (19.20)

20. Применение H₃(x) для получения оценки погрешности квадратурной формулы Симпсона.

См. [8, стр. 166].

Формула численного интегрирования на одном элементарном отрезке [х_i;x_i+1] длины h имеет вид

. (20.1)

Представим f(x) в виде f(x)=H₃(x)+r(x), где H₃(x) - многочлен Эрмита, а r(x) - погрешность интерполирования. Поскольку формула Симпсона точна для любого многочлена третьей степени, то погрешность формулы (20.1) равна

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

Список файлов ответов (шпаргалок)