Лекция 1 Приближённые методы решения слау

• Название: Лекция 1 Приближённые методы решения слау
• Дата: 29.10.2018
• Размер: 0.74 Mb.
• Имя файла: 1 (1).doc
• Тип: Лекция; #54831
• страница: 1 из 4

Лекция 1

Приближённые методы решения СЛАУ

А) Метод простых итераций. (Метод последовательных приближений).

Пусть дана система n линейных уравнений с n неизвестными:

(1)

или где - заданные числа; .

Задаются произвольно n-чисел – нулевое приближение искомой функции.

Далее подставляем в правую часть системы (1) нулевое приближение и находим первое приближение.

, (2)

Затем по 1-ому приближению находят 2-ое, 3-е и т.д.

В результате для k-ого приближения получаем формулу:

, (2’)

Таким образом мы получили последовательность векторов

Х⁽⁰⁾,Х⁽¹⁾,…, Х^(К), к=1,2,…

Если любая из таких последовательностей {Х_i^(к)} сходится некоторому пределу x_i^k = c_i , ,то данный вектор с_i, является решением сист. (1)

В равенстве (2’) перейдем к пределу при k→∞ при замене х_i на с_i.



Теорема(достаточные условия сходимости простой итерации):

Пусть выполняется хотя бы одно из следующих условий (нормы матрицы):

а) Если максимум суммы модулей коэффициентов при неизвестных (по строкам) меньше 1:

б) Если максимум суммы модулей коэффициентов при неизвестных (по столбцам) меньше 1:

в) Если сумма всех элементов в квадрате меньше 1.



Если выполняется хотя бы одно, тогда справедливы утверждения:

1. 
   система (1) имеет единственное решение (С₁,... С_n);
   
2. 
   последовательность , где i = определяется по формуле (2), при любом начальном приближении сходится к соответствующим компонентам точного решения. i =
   
3. 
   для приближенного равенства верны оценки (x₁^(k),…x_n^(k))(C_1,…C_n),
   

а’) есливыполняется условие а), то

,

б’) если выполняется условие б), то

,

в’) если выполняется условие в), то

.
Замечания:

1)Если нет никакой информации о точном решении СЛАУ, то за начальное приближение выбираем столбец свободных коэффициентов. (из приведенной матрицы);

2)остановка вычислений производной по заданной величине абсолютной погрешности и приведенным в теореме оценкам.


Б) Метод Зейделя.

Этот метод является модификацией МПИ и заключается в том, что при вычислении (к+1) приближения неизвестного х_i (i>1), используются уже вычисленные ранее (к+1) приближения неизвестных х₁, х₂,…, х_i-1

Рассмотрим систему: i=1,n

Пусть матрица α удовлетворяет одному из условий теоремы:

Если, а) <1 (коэффициенты по строкам)

б) <1 (коэффициенты по столбцам)

в)<1 (все коэффициенты)
тогда общая формула метода Зейделя имеет вид:

к=1,2…
Замечание: метод Зейделя обычно, но не всегда сходится к точному решения быстрее, чем МПИ
Лекция 2.

Интерполяция, аппроксимация.
Предполагается, что функция задана в виде таблицы конечного числа точек:

х	х0	х1	…	хn	,
у	y0	y1	…	yn

например, получена экспериментально или по известной (достаточно сложной) формуле для . Здесь х_i и y_i (i=0,1,…, n) – произвольные числа и при этом все х_i различны и упорядочены: . При этом множество всех узлов х_iназывают сеткой, если узлы являются равноотстоящими, т.е. х_i= х₀+ih, где .

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

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

При расчетах чаще всего нельзя заранее предсказать оптимальный режим вычислений, т.е. указать минимальную разрядность счета (начав с какой-либо) до тех пор, пока, не добьются удовлетворительных результатов, т.е. совпадения цифр в требуемых разрядах результата.

Определение 1. Функция называется интерполяционной для , если выполнены условия: , i=0,1, …, n, т.е график проходит через все заданные точки .

Известно, что для данной таблицы всегда существует и притом единственны интерполяционный многочлен (ИМ) степени n. Будем обозначать ИМ через . Для него верно:

,

i=0,1, …, n.

(1)

Остаточный член для , т.е. величина , имеет вид:

(2)

где П_n+1(x)=(x-x₀)(x-x₁)…(x-x_n).

Так как точка ξ практически всегда неизвестна, то при оценке погрешности для пользуются неравенством:

.

(2´)

А) ИМ Лагранжа имеет вид:

,

(3)

где .
В) ИМ Ньютона
ИМ Ньютона строятся на сетке и выражаются через конечные разности.
Определение 2. Величина называется конечной разностью первого порядка функции в точке с шагом h. По аналогии имеем: 2-ая конечная разность – это , …,

k-ая конечная разность – это .

Конечные разности удобно записывать в виде таблицы 1 (в каждом столбце, кроме столбца , из последующего числа вычитается предыдущее число и разность записывается в следующем столбце).

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

xi	yi	Δ yi	Δ2 yi	Δ3 yi	Δ4 yi	…
x0	y0	Δ y0	Δ2 y0	Δ3 y0	Δ4 y0	…
x1	y1	Δ y1	Δ2 y1	Δ3 y1	…
x2	y2	Δ y2	Δ2 y2	…
x3	y3	Δ y3	…
x4	y4	…
…	…

1-ый ИМ Ньютона имеет вид:

.

(4)

ИМ Ньютона играет в численном анализе роль, аналогичную роли формулы Тейлора в математическом анализе. Так при использовании формулы (4), если слагаемые, начиная с какого-то номера становятся малыми, то ими пренебрегают.

Если ввести обозначение: t=(x-x₀)/h, то 1-ый ИМ Ньютона примет вид:
(5)

0 ≤ t ≤ n; t=(x-x₀)/h

Оценка погрешности:
; 0 ≤ t ≤ n; x є [x₀;x_n], μ=max│f⁽ⁿ⁺¹⁾(x)│
Если ввести обозначение: t=(x-x_n)/h, то получим 2-ый ИМ Ньютона:
(6)

─ n ≤ t ≤ 0; t=(x-x_n)/h