Интерполяционная формула Лагранжа

у

a b х

представим уравнение сплайна y = a_i+b_ix, найдем коэффициенты сплайна a_i b_i. Используем условие непрерывности:

y_i = a_i+b_ix,

y_i+1 = a_i+b_i+1x

отсюда найдем, что

Function Spline1 (x, y: array of double; n: integer; xt: double): double.

Метод №3

Сплайны третьей степени

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

- условие непрерывности для каждого узла;

- условие непрерывности для первой производной;

- условие непрерывности для второй производной.

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

Метод №4

Метод наименьших квадратов

Полином Лагранжа и сплайн в точности проходят через точки {x_i, y_i} такой подход, при построении (аппроксимации) не всегда оправданы, дело в том, что данные {x_i, y_i} полученные экспериментально имеют определенную погрешность, поэтому аппроксимируемая зависимость не обязана с точностью проходить через экспериментальные точки, а только по возможной близости к ним. Пусть аппроксимируемая зависимость имеет вид y = f(x) следовательно, ∆ y = y_i - f(x_i), величина характеризует отклонение экспериментальных данных от аппроксимирующей зависимости эта величина положительна и отрицательна, что делает ее неудобно в качестве меры близости. Удобней использовать квадрат этой величины. Для того, чтобы аппроксимирующая функция была по возможности близкой ко всем экспериментальным точкам эта величина должна быть S = ∑ (y_i – f(x_i))² минимальной. Метод, имеющий значение минимума и называется методом наименьших квадратов. Обычно аппроксимирующую зависимость выбирают из некоторого класса функций зависящих от определенного числа параметров y = f(a, b, c, …, x). Параметры a b c подбирают таким образом, чтобы обеспечить минимум значение S = ∑ (y_i – f(x_i))². Используя значение минимума для функции, зависящей от нескольких переменных получим систему уравнений для нахождения параметров a, b, c…

…..

Мы получили систему, число уравнений которой равно числу параметров.

Наиболее часто экспериментальные функции аппроксимируют линейной функцией, в этом случае

Перепишем полученную систему:

a (∑ x²_i) + b(∑ x_i) = ∑ y_i x_i

a (∑ x_i) + bn = ∑ y_i

Получили систему уравнений с двумя неизвестными a и b

Аналогичным образом можно получить аппроксимирующую зависимость в виде полинома y = a₀+a₁x+a₂x²+…+a_mx^m, где m ≤ n – 1

Метод наименьших квадратов можно использовать так же при получении нелинейных двух параметрических аппроксимирующих зависимостей. Вид аппроксимирующих зависимостей может быть заранее известен по некоторым физическим соображениям. Часто физическая зависимость имеет экспоненциальный вид y = be^ax.

Эту зависимость можно привести к линейной: lny = ax + lnb: Y = AX + B

Используя экспериментальны данные мы строим экспоненциальные данные следующим образом:

{x_i, y_i} = {X_i, Y_i} = {x_i, lny_i}

AB = (a, b), a = A, b = e^B

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

Тема 3:

Решение нелинейных уравнений

Задача нахождения корней нелинейного уравнения возникает достаточно часто F(x)=ax + b, F(x)=0. Нелинейные уравнения делятся на алгебраические и трансцендентные. Для алгебраического уравнения f(x) – полином некоторой степени больше 1. Хотя алгебраические и трансцендентные уравнения часто решаются одинаковыми методами, на существуют численные методы, использующие свойства алгебраических уравнений, методы решения делятся на прямые и итерационные. Прямые методы позволяют найти решения уравнений непосредственно с помощью формул. В итерационных методах задается процедура решения в виде многократного применения. Некоторые процедуры в этом случае нахождение корня уравнения состоит из двух этапов:

1) отыскание приближенного значения корня или содержащего его отрезка;

2) уточнение значения корня до некоторой заданной точности.

Приближенное значение корня может быть найдено различными способами:

1) из физических соображений;

2) из решения аналогичной задачи;

3) графическим методом.

Если удалось найти две точки образующие отрезок [a, b] на концах которого F(x) имеет различные знаки, то в качестве начального приближения можно взять середину этого отрезка. Итерационный процесс состоит в последовательном уточнении начального приближения, каждый такой шаг называется итерацией. В результате получается последовательность приближенных значений корня. Если эта последовательность с ростом n приближается к истинному значению корня, то итерационный процесс сходится. К сожалению, часто бывает, что итерационный процесс не сходится.

Простроим график функции y = F(x)

y

y

a b

0 x

Если разный знак, то это гарантирует что будет один корень.

Метод №10

Метод половинного деления

Этот метод является одним из простейших методов решения нелинейных уравнений.

Допустим, что нам удалось найти отрезок, на концах которого функция f(x) имеет разный знак. В этом случае можно быть уверенным, что на [a, b] содержится хотя бы один корень уравнения. a< c< b.

y y=F(x)

a c b

0 x

В качестве начального приближения берем точку середине отрезка[a, b]. Получаем два отрезка [a, x₀] и [x₀, b], затем проверяем, на концах какого из этих двух отрезков функция F(x) имеет разный знак. Если знак у F(x) разный на [a, x₀], то мы полагаем b=x₀ и получаем новый отрезок [a, b], если знак разный на [x₀, b], то полагаем что a=x₀. Полученный сокращенный отрезок [a, b] делим пополам и получаем х₁.

If F(a)*F(x_i)< 0 then

b: =x[i]

else a: =x[i];

x[i+1]: =(a+b)/2

ε =|x[i+1]-x[i]|

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

Метод №11

Метод простых итераций

Представим нелинейное уравнение F(x)=0 в виде x=f(x) это преобразование можно сделать различными способами:

Например

x=F(x)+x=f(x)

Пусть х₀ является нулевым приближением корня этого уравнения. Тогда в качестве первого приближения берем x₁=f(x₀), а второго x₂=f(x₁).

Допустим, мы нашли приближенное значение: x_i+1=f(x_i).

Проиллюстрируем этот метод графически

у

у=х

у=f(x)

0 х₂ х₁ х₀ х

Итерационный процесс сходится.

у у=f(x)

y=x

0 с х₀ х₁ х₂ х

Итерационный процесс расходится.

Для сходимости итерационного процесса достаточно чтобы выполнялось условие |f^/(x)|< 1, при всех значениях х_i, в противоположном случае итерационный процесс может расходиться.

Сходимость метода может зависеть от удачного преобразования от F(x) = 0, и - это

Метод №12

Метод хорд

Предполагаем, что мы нашли отрезок [a, b] на концах которого функция F(x) меняет знак

y

B

0 a c b x

A

В методе хорд, как и в методе половинного деления на каждом итерационном шаге происходит последовательное сужение отрезка [a, b] содержащего корень. В методе хорд на каждом итерационном шаге в качестве одного из концов такого суженного отрезка берется точка пересечения хорды АВ с осью х.

Получим соотношение для определения точки С.

[a, x_i], [x_i, b]

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

Метод №13

Метод Ньютона (касательных)

Метод Ньютона сходим с методом хорд. Его отличие от метода хорд состоит в том, что на каждом итерационном шаге вместо хорды проводится касательная к кривой y=f(x) и ищется точка пересечения касательной с осью абсцисс, которая и определяет следующее приближение корня.

y y=f(x)

α

0 x_i+1 x_i x

Получим формулу для определения корня на i+1 итерационном шаге.

На каждом итерационном шаге объем вычислений в методе Ньютона несколько больше, чем в ранее рассмотренных методах, потому что приходится находить значение функции F(x), по ее производной. Однако скорость сходимости метода Ньютона в ряде случаев значительно выше, чем в других методах. Поэтому метод Ньютона является одним из самых распространенных методов решения нелинейных уравнений. Сходимость метода Ньютона в значительной степени зависит от выбора начального приближения х₀. Чем ближе х₀ к корню, тем сходимость лучше, поэтому иногда целесообразно использовать смешанный алгоритм. Во всех итерационных процессах ошибка округления не накапливается – это является одним из важнейших преимуществ итерационных методов.

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

Корни алгебраического уравнения в ряде случаев можно находить последовательно. Предположим сначала методом половинного деления нашли корень уравнения x_i, после этого получаем:

Тема 4:

Решение систем линейных уравнений

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

Задачи на нахождение собственных значений так же приводят к СЛАУ. Таким образом, решение СЛАУ – одна из самых распространенных и важных задач высшей математики.

Важнейшей характеристикой квадратной матрицы является ее определитель(D)

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

Если определитель системы D=0, то в этом случае матрица D называется вырожденной, а системы либо не имеют решения, либо имеет бесчисленное множество решений. Для некоторых систем оказывается очень чувствительны к малым погрешностям исходных данных. Такие системы называются условнообустроенные. Определение плохо обусловленных систем близок к нулю. Всегда надо иметь в виду это. Некоторые неконкретные задачи приводят к плохо обусловленным системам уравнений. Эти задачи могут иметь важное практическое значение. Существуют методы решения таких задач. Методы решения систем уравнений делятся на 2 большие группы: прямые и итерационные. Прямые методы используют методы, которые наиболее универсальны, но они образуются недостатками: они требуют хранения в оперативной памяти сразу всей матрицы, поэтому прямые методы используют обычно, если n не превосходит несколько 100. В итерационных методах решение находится путем последовательности, в этих методах накопленная погрешность не превосходит, поэтому их можно использовать для решения больших систем уравнений. Однако сходимость итерации может быть очень медленно. Время счета может оказаться слишком большим. В них решаются ограниченный класс уравнений. Метод Крамера относится к прямому методу, однако, на практике метод Крамера практически некогда не используется, так как он требует большого объема вычислений. Оценим объем вычислений методом Крамера: N=(n+1)n n! n с ростом n малое резко возрастает n=6 N> 10000000.

Метод №14

Метод Гаусса

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

Сначала на первом шаге с помощью первого уравнения исключается х первое из всех последовательных уравнений системы, в результате получается новая система, имеющая то же решение, но в первом столбце матрицы будет не нулевой только первый, а все остальные обращаются в нуль. На втором шаге исключается х₂ из всех уравнений. Этот процесс продолжается до тех пор, пока в левой части последовательного n-го уравнения остается лишь один член с неизвестным х_n.

Рассмотрим процесс исключения подробнее. На к-ом шаге используется х_k. Запишем k-ое уравнение

Исключим с помощью этого уравнения x_k из уравнения с номером i> k

Из i-го уравнения вычитаем k-ое умножимое на a_ik/a_kk после такого вычисления первое слагаемое сокращается. Запишем значение аргумента перед х.

при этом изменится свободный член:

По завершению прямого хода получается система с треугольной матрицей. Далее производится обратный ход метода Гаусса. Он состоит в последовательном вычислении малых неизвестных начиная с х_n. Сначала находится

Далее используя это значение, находится х_n-1 и док далее. На k-ом шаге обратного хода неизвестные находятся с помощью выражения: . В процессе исключения неизвестных приходится делить. Чтобы исключить эту ситуацию необходимо на каждом шаге прямого хода метода Гаусса менять расположение, чтобы a_kk≠ 0, а лучше, чтобы он имел максимально возможное значение. Переустановка уравнений должна быть предусмотрена в одном из уравнений и метод Гаусса, в котором производится перестановка уравнений таким образом, чтобы диагональный элемент имел значение, называемый элементом Гаусса с главным значением. В методе Гаусса объем вычислений пропорционален n³. Существуют практически значимые случаи, когда объем вычислений систем линейных уравнений можно резко сократить.

Метод №15

Метод прогонки

Метод прогонки является модификацией метода Гаусса для частного случая систем уравнений с трех диагональной матрицей. Такие системы возникают при численном решении уравнений математической физики. Коэффициент сплайна третьей степени находится путем решения систем с трех диагональной матрицей. В методе прогонки объем вычислений растет пропорционально n. Запишем систему уравнений, которая решается методом прогонки:

Общий вид уравнения:

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

Рассмотрим первый этап (прямой ход):

Для этого неизвестное x_i выражаем через x_i+1 таким образом x_i , где A_i и B_i неизвестные пока коэффициенты (прогоночные). На первом этапе как раз и находятся A_i и B_i. Сравним x_i = A_ix_i+1 + B_i, i=1, x₁ = A₁x₂ + B₁

Запишем i-ое уравнение системы, выразим в нем x_i-1 с помощью

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

После того как найдены все прогоночные коэффициенты, в результате прямого хода метода находим х_n, для этого сравниваем последнее уравнение системы a_nx_n-1 + b_nx_n = d_n с последним прогоночным соотношением x_n-1 = A_n-1x_n + B_n-1 получается система: .

Метод №16