Численные методы решения типовых математических задач

курсовая работа

1.4 Численный метод решения задачи

Разрешим систему относительно неизвестных при ненулевых диагональных элементах , aii?0, i= 1,n (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора в и матрицы б эквивалентной системы:

При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.

В качестве нулевого приближения x(0) вектора неизвестных примем вектор правых частей x(0)=в. Тогда метод простых итераций примет вид:

Из (1.19) видно преимущество итерационных методов по сравнению, например, с рассмотренным выше методом Гаусса. В вычислительном процессе участвуют только произведения матрицы на вектор, что позволяет работать только с ненулевыми элементами матрицы, значительно упрощая процесс хранения и обработки матриц.

Имеет место следующее достаточное условие сходимости метода простых итераций.

Метод простых итераций (1.19) сходится к единственному решению СЛАУ при любом начальном приближении x(0), если какая-либо норма матрицы б эквивалентной системы меньше единицы

Если используется метод Якоби (выражения (1.18) для эквивалентной СЛАУ), то

достаточным условием сходимости является диагональное преобладание матрицы A, т.е.

(для каждой строки матрицы A модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае ||б||c меньше единицы и, следовательно, итерационный процесс (1.19) сходится.

Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.19) необходимо и достаточно, чтобы спектр матрицы б эквивалентной системы лежал внутри круга с радиусом, равным единице.

При выполнении достаточного условия сходимости оценка погрешности решения на k- ой итерации дается выражением:

где x·- точное решение СЛАУ.

Процесс итераций останавливается при выполнении условия , где ее?)(kе - задаваемая вычислителем точность.

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

откуда получаем априорную оценку числа итераций k при ||б||<1

Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется на практике.

1.6 Текст программы

program Yakobi;

uses crt;

const

maxn=100;

type

matrix=array[1..maxn,1..maxn] of real;

vector=array[1..maxn] of real;

vector1=array[1..maxn] of real;

var

i,j,n,k1: integer;

e,norma:real;

a: matrix;

b: vector;

x2,x3: vector1;

imya,dannble_i_rezultat,ekran:string;

procedure input(var kolvo:integer; var pogreshnostb:real; var matr1:matrix; var matr2:vector);

{Ввод исходных данных}

var i,j,code:integer;

a_s: string;

b_s: string;

begin

writeln(введите количество уравнений);

readln(kolvo);

writeln(введите погрешность вычисления);

readln(pogreshnostb);

writeln(введите матрицу коэффициентов при неизвестных);

for i:=1 to kolvo do

for j:=1 to kolvo do

begin

repeat

begin

writeln(введите элемент [,i,,,j,] и нажмите Enter);

readln(a_s);

if (i=j) and (a_s=0) then

repeat

begin

writeln(Элементы на главной диагонали должны быть отличны от нуля. Повторите ввод);

readln(a_s);

end;

until a_s<>0;

val(a_s,matr1[i,j],code);

end;

until code=0;

end;

writeln(введите вектор свободных коэффициентов);

for j:=1 to kolvo do

begin

repeat

writeln(введите элемент ,j, и нажмите Enter);

readln(b_s);

val(b_s,matr2[j],code);

until code=0;

end;

end;

1.7 Тестовый пример

2. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями

2.1 Постановка задачи

Разработать схему алгоритма и написать программу на языке Turbo Pascal 7.0 для интерполирования функции, заданной в узлах, используя метод Ньютона с разделенными разностями.

2.2 Математическая формулировка задачи

Дана табличная функция:

i

xi

yi

0

x0

y

1

x1

0

2

x2

y

 ...

 ...

1

n

xn

y

 

 

2

 

 

 ...

 

 

y

 

 

n

или

Точки с координатами (xi, yi) называются узловыми точками или узлами.

Количество узлов в табличной функции равно N=n+1.

Необходимо найти значение этой функции в промежуточной точке, например, x=D, причем .

Для решения задачи строим интерполяционный многочлен.

2.3 Обзор существующих численных методов решения задачи

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

Интерполяционный многочлен может быть построен при помощи специальных интерполяционных формул Лагранжа, Ньютона, Стерлинга, Бесселя и др.

Интерполяционный многочлен по формуле Лагранжа имеет вид:

Докажем, что многочлен Лагранжа является интерполяционным многочленом, проходящим через все узловые точки, т.е. в узлах интерполирования xi выполняется условие Ln(xi) = yi. Для этого будем последовательно подставлять значения координат узловых точек таблицы в многочлен (2.1). В результате получим:

если x=x0, то Ln(x0) = y0,

если x=x1, то Ln(x1) = y1,

……………

если x=xn, то Ln(xn) = yn.

Это достигнуто за счет того, что в числителе каждой дроби при соответствующем значении уj, j=0,1,2,…,n отсутствует сомножитель (x-xi), в котором i=j, а знаменатель каждой дроби получен заменой переменной х на соответствующее значение хj.

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

Чем больше узлов интерполирования на отрезке [x0,xn] , тем точнее интерполяционный многочлен приближает заданную табличную функцию, т.е. тем точнее равенство:

Однако с увеличением числа узлов интерполирования возрастает степень интерполяционного многочлена n и в результате значительно возрастает объем вычислительной работы. Поэтому при большом числе узлов необходимо применять ЭВМ. В этом случае удобно находить значения функции в промежуточных точках, не получая многочлен в явном виде.

При решении задачи экстраполирования функции с помощью интерполяционного многочлена вычисление значения функции за пределами отрезка [x0,xn] обычно производят не далее, чем на один шаг h, равный наименьшей величине

так как за пределами отрезка [x0,xn] погрешности, как правило, увеличиваются.

Интерполяция по Ньютону

Интерполяционный многочлен по формуле Ньютона имеет вид:

(2.2)

где n - степень многочлена,

- разделенные разности 0-го, 1-го, 2-го,…., n-го порядка, соответственно.

Сплайн-интерполяция

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

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

Например, для некоторых функций (рис.) необходимо задать все кубические функции q1(x), q2(x), …qn(x).

В наиболее общем случае эти многочлены имеют вид:

где kij - коэффициенты, определяемые описанными ранее условиями, количество которых равно 4n. Для определения коэффициентов kij необходимо построить и решить систему порядка 4n.

Первые 2n условий требуют, чтобы сплайны соприкасались в заданных точках:

Следующие (2n-2) условий требуют, чтобы в местах соприкосновения сплайнов были равны первые и вторые производные:

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

При построении алгоритма метода первые и вторые производные удобно аппроксимировать разделенными разностями соответствующих порядков.

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

Делись добром ;)