- •Лекция 1 Приближённые методы решения слау
- •В) Метод Гаусса. (Метод последовательного исключения переменных)
- •Прямой ход.
- •Формулы прямого хода
- •Обратный ход
- •Формулы обратного хода.
- •Интерполяция, аппроксимация.
- •Оценка погрешности:
- •Приближённое интегрирование функций
- •1) Интегрирование по методу прямоугольников.
- •2) Интегрирование по методу трапеций.
- •3) Интегрирование по методу Симпсона.
- •2.1) Отделение корней.
- •Уточнение корней до заданной точности.
- •1) Метод половинного деления (дихотомии).
- •2) Метод хорд.
- •2) Метод Ньютона (касательных).
- •4) Комбинированный метод (хорд и касательных).
- •Постановка задачи.
- •1Ый усовершенствованный метод Эйлера.
- •2Oй усовершенствованный метод Эйлера.
- •Многошаговые методы.
Прямой ход.
Это основной этап решения системы уравнений с помощью метода Гаусса. Его суть состоит в приведении исходной расширенной матрицы системы к верхнетреугольной матрице с помощью эквивалентных преобразований (добавление к строке любой линейной комбинации других строк и перестановка строк, т.е. уравнений). Формулы прямого хода соответствуют последовательному выражению переменных из уравнений и подстановке их в последующие уравнения, т.е. их фактическому исключению из последующих уравнений системы. При этом шагом считается исключение одной переменной из всех последующих уравнений системы.
Рассмотрим k-ый шаг прямого хода. На k-ом шаге матрица системы имеет вид:
(а11 а12 … а1k … a1n | b1)
(0 a22 … a2k … a2n | b2)
(0 … … … … … )
(0 0 … akk … akn | bk)
(0 … … … … … )
(0 0 … ank … ann | bn)
Осталось n-k+1 неизвестных. Чтобы удалить х(k) из последней строчки, например, надо из нее вычесть k-ую строчку с таким коэффициентом, чтобы получить на месте аnk ноль. Для этого коэффициент должен быть равен cnk=ank/akk. Элемент аkk называется разрешающим элементом k-ого шага и должен быть отличен от 0.
Формулы прямого хода
cmk=amk/akk где 1<=k<n
bm=bm-cmkbk, k<m<=n
aml=aml-cmkakl, k<=l<=n
Обратный ход
Последовательное вычисление значения неизвестных xn, xn-1,..., х1 (именно в таком порядке) для полученной после прямого хода верхнетреугольной системы называется обратным ходом.
Формулы обратного хода.
,откуда получаем:
для k=n,n-1,…,1.
Лекция 2.
Интерполяция, аппроксимация.
«Интерполяционный многочлен»
Предполагается, что функция задана в виде таблицы конечного числа точек:
х |
х0 |
х1 |
… |
хn |
, |
у |
y0 |
y1 |
… |
yn |
например, получена экспериментально или по известной (достаточно сложной) формуле для . Здесьхi и yi (i=0,1,…, n) – произвольные числа и при этом все хi различны и упорядочены: . При этом множество всех узловхi называют сеткой, если узлы являются равноотстоящими, т.е. хi= х0+ih, где .
Используя исходные данные, затем подбирают функцию несложного вида, значения которой приявляются приближенными для.
Важным здесь следует отметить не только то, чтобы имела простой вид и хорошо приближала, но и чтобы ее практически можно было найти. В этом смысле наиболее подходящий вид для- многочлен. Но и в этом случае не все просто с вычислительной стороны. Как правило, при нахождении значенийнельзя обойтись без многочисленных промежуточных округлений числе, что часто приводит к большой потере точности коэффициентов. И может случиться так, что полученный в результате многочлен будет гораздо хуже приближать данную функцию, чем истинный многочлен, а это недопустимо.
При расчетах чаще всего нельзя заранее предсказать оптимальный режим вычислений, т.е. указать минимальную разрядность счета (начав с какой-либо) до тех пор, пока, не добьются удовлетворительных результатов, т.е. совпадения цифр в требуемых разрядах результата.
Определение 1. Функция называется интерполяционной для, если выполнены условия:,i=0,1, …, n, т.е график проходит через все заданные точки.
Известно, что для данной таблицы всегда существует и притом единственны интерполяционный многочлен (ИМ) степени n. Будем обозначать ИМ через . Для него верно:
, |
i=0,1, …, n. |
(1) |
Остаточный член для , т.е. величина , имеет вид:
(2) |
где Пn+1(x)=(x-x0)(x-x1)…(x-xn).
Так как точка ξ практически всегда неизвестна, то при оценке погрешности для пользуются неравенством:
. |
(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-x0)/h, то 1-ый ИМ Ньютона примет вид:
(5)
0 ≤ t ≤ n; t=(x-x0)/h
Оценка погрешности:
; 0 ≤ t ≤ n; x є [x0;xn], μ=max│f(n+1)(x)│
Если ввести обозначение: t=(x-xn)/h, то получим 2-ый ИМ Ньютона:
(6)
─ n ≤ t ≤ 0; t=(x-xn)/h