С.) «МЕТОД НАИМЕНЬШИХ КВАДРАТОВ»

Стр 1 из 3Следующая ⇒

Лекция 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.

Интерполяция, аппроксимация.

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

х	х₀	х₁	…	х_n	,
у	y₀	y₁	…	y_n	,

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

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

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

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

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

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

i=0,1, …, n.

(1)

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

(2)

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

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

(2´)

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

(3)

где .

В) ИМ Ньютона

ИМ Ньютона строятся на сетке и выражаются через конечные разности.

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

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

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

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

Таблица 1

x_i	y_i	Δ y_i	Δ² y_i	Δ³ y_i	Δ⁴ y_i	…
x₀	y₀	Δ y₀	Δ² y₀	Δ³ y₀	Δ⁴ y₀	…
x₁	y₁	Δ y₁	Δ² y₁	Δ³ y₁	…
x₂	y₂	Δ y₂	Δ² y₂	…
x₃	y₃	Δ y₃	…
x₄	y₄	…
…	…

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

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

; -n ≤ t ≤ 0; x є [x₀;x_n], μ=max│f⁽ⁿ⁺¹⁾(x)│

С.) «МЕТОД НАИМЕНЬШИХ КВАДРАТОВ»

Перечислим особенности, на которые надо обратить внимание при выполнении задания по этой теме.

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

х_i	х₀	х₁	…	х_n	,
у_i	y₀	y₁	…	y_n	,

например, получена экспериментально, где x_i, y_i (i=1,…,n) – произвольные числа. При этом все

числа x_i различны.

Пусть также имеется некоторая функция , определенная для всех значений x_i (i=1,…,n).

Определение 3. Число Т, где

(7)

называется среднеквадратичным (или среднеквадратическим) уклонением функции от заданной .

Наряду с числом Т вводят также вспомогательную величину

(8)

Функцию стараются подобрать, чтобы число Т получилось достаточно малым.

Можно предложить следующие способы выбора функции .

Способ 1. , (9)

т.е. - многочлен степени m, при этом m<n.

Способ 2. , здесь - сплайн, т.е. кусочно-полиномиальная гладкая функция.

Способ 3. , (10)

т.е. - частичная сумма ряда Фурье, при этом m – четно и m<n.

Перечисленные способы 1-3 задают для вид приближающей функции , которая, в свою очередь, зависит от коэффициентов (или параметров) a_i. Лучшим набором коэффициентов a_i считается тот, для которого величина w из (8) меньше.

Определение 4. Говорят, что функция найдена для по методу наименьших квадратов (МНК), если она дает минимально возможное значение величины w в соотношении (8).

Примечание. Заметим, что при m=n-1 многочлен , полученный по МНК, совпадает с интерполяционным многочленом и, следовательно, соответствующее среднеквадратичное уклонение (теоретически) равно числу . При использовании в расчетах ЭВМ это уклонение, как правило, получается числом, отличным от нуля.

Рассмотрим в качестве приближающей функции многочлен степени m, который имеет вид

Согласно методу наименьших квадратов наилучшими коэффициентами считаются те, для которых сумма квадратов уклонений будет минимальной, т. е.

Т есть функция коэффициентов . Наряду с функцией Т рассматривают функцию S вида:

Очевидно, что S и Т достигают своего минимума в одной точке. Далее для отыскания точки минимума будем рассматривать функцию S, поскольку она удобнее для вычислений.

При данной приближающей функции критерий близости, который используется в методе наименьших квадратов, запишется следующим образом:

(11)

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

(12)

То есть:

(13)

Лекция 3

ПРИБЛИЖЁННОЕ ИНТЕГРИРОВАНИЕ ФУНКЦИЙ

Общие замечания.

Если функция f(x) непрерывна на отрезке [a, b] и известна её первообразная F(x), то определённый интеграл от этой функции в пределах от a до b может быть вычислен по формуле Ньютона- Лейбница

, (1)

где F′(x) = f(x).

Однако во многих случаях первообразная функция F(x) не может быть найдена с помощью элементарных средств или является слишком сложной; вследствие этого вычисление определённого интеграла по формуле (1) может быть затруднительным или даже практически невыполнимым.

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

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

Обычный приём при численном вычислении однократных интегралов.

Отрезок [a, b] разбивают на части (чаще всего равные) точками х_j ( j = ) так, что a = x₀< x₁< x₂…< x_n= b, и в узлах х_j находят значения у_j = f(x_j). Функцию f(x) заменяют интерполирующей или аппроксимирующей функцией простого вида (например, полином) такой, что она легко интегрируется.

Мы получаем квадратурные формулы:

, (2)

где х_j − выбранные узлы интерполяции,

А_j − коэффициенты, зависящие только от выбора узлов, но не от вида функции, R − остаточный член, или погрешность квадратурной формулы.

1) Интегрирование по методу прямоугольников.

Метод прямоугольников − простейший приём численного интегрирования, при котором функция f(x) заменяется интерполяционным многочленом

нулевого порядка. Интервал интегрирования [a,b] делится точками х₀, х₁, …, х_n на n равных частей (рис. 1), причём х₀ = a, x_n= b, длина каждой части составляет h = (b-a)/n, и тогда x_i = x₀+ih, i = 0, …, n.

Из каждой точки х проведём перпендикуляр до пересечения с кривой f(x),

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

Рис.1. Геометрическая интерпретация интегрирования по методу прямоугольников.

Площадь полученной ступенчатой фигуры можно найти как сумму площадей прямоугольников, стороны которых равны h и у_i. Следовательно, площадь отдельного прямоугольника составит S_i = y_i∙h,

тогда

Следовательно, формула вычисления определённого интеграла по методу прямоугольников имеет вид:

(3)

Остаточный член имеет вид: (4)

2) Интегрирование по методу трапеций.

Метода трапеций заключается в линейной аппроксимации f(x) на отрезке [a,b]. Участок интегрирования также разбивается на n равных частей. Если провести ординаты во всех точках деления и заменить каждую из полученных криволинейных трапеций прямолинейной (рис.2), то приближённое значение интеграла будет равно сумме площадей прямолинейных трапеций.