Методы компьютерных вычислений и их приложение к физическим задачам 2 (стр. 5 из 12)

На практике для обеспечения сходимости итерационных методов необходимо, чтобы значения диагональных элементов матрицы СЛАУ были преобладающими по абсолютной величине по сравнению с другими элементами.

Представим СЛАУ в следующей форме, удовлетворяющей (3):

(4)

Зададим начальные приближения

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

К ускорению сходимости приводит использование приближения к решениям путем последовательного уточнения компонентов, причем k-я неизвестная находится из k-го уравнения. Такая модификация итерационного метода носит название метода Зейделя:

Критерий сходимости метода Зейделя: Пусть

– вещественная симметричная положительно определенная матрица. Тогда метод Зейделя сходится.

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

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

1) Необходимость: приблизить f(x) более простой функцией ф(х), совпадающей в узлах x_i с f(x_i), если f(x) определена только в узловых точках (результат эксперимента) или очень сложно вычисляется.

Условия Лагранжа

ф(х, с₀, с₁…с_n) = f_i, 0 <_{_}i < n,

где с_i - свободные параметры, определяемые из данной системы уравнений.

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

2) Пусть ф (х) = с₀ + с₁х + с₂х² +…+ с_nxⁿ (канонический вид полинома) ;сетка узлов может быть неравномерной. Получившаяся СЛАУ относительно свободных параметров сi имеет решение, если среди узлов х_i нет совпадающих.Ее определитель – определитель Вандермонда:

Общая блок-схема:

3) Пусть задано n+1 значение функции f(x) в узлах x_j

ф(х) = P_n(х) =

_i (x-x_j)/(x_i-x_j) - полином Лагранжа

Преимущества: потребуется решать СЛАУ для определения значения полинома в точке х.

Недостатки: для каждого х полином требуется читать заново.

Погрешность формулы:

(*)

Увеличение числа узлов и, соответственно, степени полинома P_n(x) ведет к увеличению погрешности из-за роста производных

.

4) ф(х) = P_n(x) = A₀+A₁(x-x₀)+A₂(x-x₀)(x-x₁)+…+A_n(x-x₀)(x-x₁)…(x-x_n-1) - многочлен Ньютона для n+1 узла.

Коэффициенты Ф представляют собой разделенные разности и записываются в виде:

А₀ = f₀

A₁ = (f₀-f₁)/(x₀-x₁) = f₀₁

A₂ = (f₀₁-f₀₂)/(x₁-x₂) = f₀₁₂, где f₀₂ = (f₀-f₂)/(x₀-x₂)

A₃ = (f₀₁₂-f₀₁₃)/(x₂-x₃) = f₀₁₂₃ , где f₀₁₃ = (f₀₁-f₀₃)/(x₁-x₃) , а f₀₃ = (f₀-f₃)/(x₀-x₃)

и в общем случае A_k = (f_01…k-1-f_01…k)/(x_k-1-x_k)

Т.е. многочлен n-й степени выражается при помощи разделенных разностей через свои значения в узлах.

Преимущества: не решается СЛАУ, однако вычисление коэффициентов полинома не зависит от значения х и может быть вычислено только один раз. При добавлении нового узла также не происходит пересчета коэффициентов, кроме последнего.

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

P₂(x) = A₀+ (x-x₀)(A₁+(x-x₂)(A₃+…)…)

Погрешность определяется тем же соотношением (*)

Входящая в состав погрешности величина

(х-х_i) = w_n(x) ведет себя при постоянном шаге так, как показано на рисунке. Многочлен Ньютона имеет погрешность 0(hⁿ⁺¹) и обеспечивает n+1-й порядок точности интерполяции.

Между разделенными разностями и производными соответствующих порядков существует соотношение f ^<n>(x) ~ n! F_01…n , где n – степень производной. Это используется в численном дифференцировании и при оценке погрешностей интерполяции.

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

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

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

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

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

Обычно для сплайна выбирают кубический полином

определенный на интервале х из [x_i-1, х_i].

При этом вся кривая представляет собой набор таких кубических полиномов, с определенным образом подобранными коэффициентами а_i , b_i , c_i , d_i , i- параметр сплайна.

Если вдоль сплайна совершается механическое движение, то непрерывность второй производной предполагает непрерывность ускорения и, следовательно, отсутствие резких изменений приложенной силы.

N+1 узлов

N интервалов

4N неизвестных

Условия подбора коэффициентов:

1)условия Лагранжа:

,

2)непрерывность первой и второй производной в узлах

ф_i’(x_i) = ф_i+1’(x_i); ф_i”(x_i) = ф_i+1(x_i)

3) условия в крайних узлах x₀ и x_n. Обычно задают условия свободных концов сплайна:

ф₁”(x₀) = 0, ф_n”(x_n) = 0

Из полученных условий определяются зависимости между коэффициентами сплайнов:

В узле х = х_i-1 коэффициент a_i = f_i-1.

В следующем узле x = x_i выполняется условие a_i+b_ih_i+c_ih_i²+d_ih_i³ = f_i,

где элементарный шаг h_i = x_i – x_i-1.

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

ф_i^/(x) = b_i+2c_i(x-x_i-1)+3d_i(x-x_i-1)² ,

ф_i^//(x) = 2c_i+6d_i(x-x_i-1);

В узле x = x_i первая производная

ф_i^/(x_i) = b_i+2c_ih_i+3d_ih_i² (1)

ф_i+1^//(x_i) = b_i+1 (2)

Приравнивая (1) и (2), получаем b_i +2c_ih_i+3d_ih_i² = b_i+1.

Вторая производная

ф_i^//(x_i) = 2c_i+6c_ih_i (3)

ф_i+1^//(x_i) = 2c_i (4)

Приравнивая (3) и (4), получаем в свою очередь c_i+3d_ih_i = c_i+1. Таким образом стыкуем все полиномы в узлах 1 ≤ i ≤ n-1. В крайних точках диапазона

ф₁^//(x₀) = 2c₁ = 0 → c₁ = 0

ф₁^//(x_n) = 2c_n+6d_nh_n = 0 → c_n +3d_nh_n = 0

Для всех 0 ≤ i ≤ n вышеприведенные соотношения представляют собой полную систему 4n линейных алгебраических уравнений относительно коэффициентов сплайнов, которую можно привести к системе ЛАУ, выразив коэффициенты a_i, b_i, d_i через c_i и решить методом Гаусса или прогонки.