Файл: 20-24.docx

Оценка скорости сходимости метода простых итераций для системы линейных алгебраических уравнений в "явной" форме. Оценка точности приближения.

Эта запись справедлива для любого p

При р→∞ получим оценку:

Таким образом:

и Скорость сходимости пропорциональна геометрической прогрессии

С другой стороны , поэтому скорость сходимости линейная (геометрическая прогрессия)

Оценка погрешности нахождения решений

1/ε

Мажоритарная оценка редко используется на практике, так как дает завышенные результаты

Опосториорная оценка:

Условия:

- оценка для z_k-1

-

Опосториорная оценка

Представление таблично заданной функций сплайнами.

g₁, g₂, … g_n - функции Сплайн

g_i = k_i1 + k_i2 x + k_i3 x² + k_i4 x³ – кубический сглаживающий сплайн

неизвестные: k_{i1 …} k_i4

Получаем (4n-2) уравнения – недостающее уравнение – уравнение производных для точки х_0, равное нулю

,

Теорема о возможности перехода от СЛАУ в «неявной» форме к СЛАУ в «явной». Матрица с диагональным преобладанием.

Теорема о возможности перехода от системы (1)Ax=y =>x=αx+β (2); ||α||<1

Для любой системы вида(1) с невырожденной матрицей возможен переход к системе (2), такой, что норма матрицы 2<1

D=A^-1 +B – невырождена по непрерывности

Dax=Dy

DetD не равен 0

(A^-1 +B)Ax=Dx

A^-1 Ax= BAx=Dy

X=-BAx+ Dy

||α||<или = ||B|| ||A||

1>||α||<или =||B|| ||A||

Теоретически такой переход всегда сущесвует. Но на практике такой переход требует:

Если А- матрица с диагональным преобладанием то переход производится тривиальным образом

|3 2 1 | Q=E-2*S*S^-T

A=|4 2 2 |

|-1 6 -1 |

A=[A1,A2,A3]

QA=Q[A1,A2,A3]

1

Q: x-> 0 *α, α=||x||

0

S- растояние от исходной матрицы до получаемой

S=(x-αy)* 1\λ

( | 3 | |1| )

S= ( | 4 | - |0| * ||x|| ) * 1\λ

( | 1 | |0| )

Теорема

Система с диагональным преобладанием всегда разрешима и притом единственным образом.

Решение системы линейных обыкновенных дифференциальных уравнений 1-ого порядка численно-аналитическим методом.

Запись Коши:

x(t)+Ax(t)=y(t)

x(0)=x0

A1x(t)+A0x(t)=y(t)

x(0)=x0

От дифференцируемого уровненияn-ого порядка можно перейти к системе nдифференцированому уравнению 1ого порядка. Решение такого уравнения ищется как сумма общих решений однородных систем.

1)A1x(t)+A0x(t)=0

x=a1e^λ1t * B1+...+ane^ λnt *Bn

det[A1 λ1+A0]=0,i=1,m

[A1 λi+A0]Bi=0, i=i,n

B,n- произв. числа

A1*d\dt *(a1e^λ1t B1+...+ ane^λntBn)+A0(a1e^λ1t B1+...+ane^λntBn)= a1e^λ1t [A1 λ1+A0]B1 +...+an^λnt (A1λ1+A0)B0=0

Если нет кратных собственных значений в матрице

Алгебраическая кратность >Геометрической кратности-диффектная матрица

Алгебраическа кратность= геометрической кратности, тогда:

m

x(t)=Σ e^λit (Bin+Bi1t+...BisT^s)ai

i=1

m-количество разных собственых значений

s-1=кратность i-того собственного знчения (геометтрич)

Метод Зейделя решения систем линейных алгебраических уравнений.

Запись итерационного стационарного процесса в канонической форме. Рассмотрим произвольную квадратную матрицу:

.

Разложим её на сумму трех матриц , где- диагональная часть матрицы, которая содержит элементы, стоящие на главной диагонали;- нижняя треугольная матрица,- верхняя треугольная матрица.

В классическом методе Зейделя, записанном в канонической форме, полагают

В результате формула принимает вид:

,

или

(*)

Перейдем от векторной формы записи рекуррентной формулы (*) к построчной:

Эти уравнения позволяют последовательно рассчитать компоненты вектора - ой итерации подобно тому, как это делалось во время обратного хода в методе Гаусса:

, .

Формула предполагает, что ,. Если матрицаудовлетворяет условиям теоремы Самарского:, то, все ее диагональные элементы должны быть строго положительными и, тем самым, не могут обращаться в ноль.

Алгоритм в методе Зейделя прост и удобен для вычислений. Он не требует никаких действий с матрицей . Ранее вычисленные на текущей итерации компонентысразу же участвуют в расчетах наряду с компонентамии, таким образом, не требуют дополнительного резерва памяти, что существенно при решении больших систем.

Сходимость метода Зейделя в случае, когда матрица удовлетворяет условию теоремы Самарского, т.е. является самосопряженной и положительно определенной. Метод Зейделя сходится для любой системы, в которой матрицаобладает свойством диагонального преобладания.

В методе Зейделя при вычислении (k+1)-го приближения неизвестных х₁, х_2,..., х_i-1 вычисления осущест­вляются следующим образом. Выбираем произвольно начальные приближения корней х₁⁽⁰⁾, х₂⁽⁰⁾_,..., х_n ⁽⁰⁾и подставляем в первое уравнение системы

(1):

х₁⁽¹⁾ = ₁ + ₁₁х₁⁽⁰⁾ + ₁₂х₂⁽⁰⁾ + … + _1nх_n⁽⁰⁾

полученное первое приближение х₁⁽¹⁾ подставляем во второе уравнение сис­темы (1):

х₂⁽¹⁾ = ₂ + ₂₁х₁⁽⁰⁾ + ₂₂х₂⁽⁰⁾ + … + _2nх_n⁽⁰⁾

Полученные первые приближения х₁⁽¹⁾ и х₂⁽¹⁾ подставляем в третье урав­нение системы (1):

Х₃⁽¹⁾ = ₃ + ₃₁х₁⁽⁰⁾ + ₃₂х₂⁽⁰⁾ + … + _3nх_n⁽⁰⁾

и т.д.

Наконец,

Х_n⁽¹⁾ = _n+ _n1х₁⁽⁰⁾ + _n2х₂⁽⁰⁾ + … + _nn-1х_n-1⁽¹⁾ + _nnх_n⁽⁰⁾ Аналогично строим вторые, третьи т.д. итерации. Таким образом, пред­полагая, что k-e приближение корней х₁^(k) известны, по методу Зейделя строим (k+l)-e приближение по следующим формулам:

…

где k= 0, 1, 2, ..., n. Объясним откуда они появляются. Зейдель рассмотрел Метод простых итераций: x^(k+1) = x^(k) + 

Зейдель предложил разбить= В+ С на сумму двух матриц. Тогда итерационная формула Метода простых итераций примет вид: x^(k+1) = Cx^(k) + 

Переносим слагаемое x^(k) в левую часть: x^(k+1) - x^(k) = Cx^(k) + 

Зейдель предложил поменять индекс kна индекс k + 1.

x^(k+1) - x^(k+1) = Cx^(k) + 

Тогда получилось соотношение: (E – B)x^(k+1) = Cx^(k) + 

Окончательно имеем:

x^(k+1) = (E – B)^(-1)Cx^(k) + (E – B)^(-1)

_zeidel = (E – B)^(-1)C

_zeidel = (E – B)^(-1)

Откуда следуют формулы приведенные выше. Преимущество метода Зейделя заключается в том, что области сходимости не совпадают, так как м. Зейделя может сходиться там, где МПИ расходиться. Число ите­раций м. Зейделя, меньше так как данные лучше подготовлены (). Скорость сходимости в м. Зейделя такая же как и в МПИ (не хуже).

Сходимость метода Зейделя

В=D+T_H; =1; A=T_H+D+Т_B

Матрица будет положительно определена, если диагональные элементы будут положительны.

Требования к выбору 

• Сходимость стационарной двухслойной схемы

• Наиболее быстрая сходимость

Требования к матрице В

Матрица-В не должна быть матрицей общего вида. Она должна быть легко обратимой, чтобы трудоемкость не превышала n² (диагональной, треугольной, их комбинацией).

Точность = kn², где (k<<n) и k - количество итераций

Оценка погрешностей выполнения арифметических операций с множеством чисел.

Выполнение операций над m числами

Ведем обозначения (ab) = (ab)(1+ε), где  => +, -, *, /

- произведение чисел

y₀ = 1; y_i = x_i·y_i-1;

пренебрегаем

Для сложения: n²ε

В заключение:

1. Математический анализ и линейная алгебра – это абстрактные модели для задач вычислительной математики (все операции не ассоциативны)

2. Программировать оценку погрешности нереально из-за сложности и увеличения затрат. Поэтому используют оценку сверху, на практике данную задачу решают изменением входных параметров итд.