Геометрическая интерпретация метода 3 страница

ð , где число шагов, необходимых для достижения точки , исходя из точки .

За начальное приближение принимаем:

Применяя метод итерации, получим:

Итерационный процесс, останавливается, когда

и тогда =>

Пример:

Горизонтальная таблица разностей:

x	y	y	2y	3y

Þ

Тогда

Обратное интерполирование для неравноотстоящих точек

Задача обратного интерполирования для случая неравноотстоящих точек непосредственно может быть решена с помощью интерполяционной формулы Лагранжа

Или с помощью интерполяционной формулы Ньютона для неравноотстоящих точек

Общие выводы по задаче интерполяции

1. Для равноотстоящих узлов интерполирования лучше всего выбирать интерполяционные формулы Ньютона, при этом:

а) если значение в начале таблицы - 1ИФН

б) если значение в конце таблицы - 2ИФН

2. Существуют интерполяционные центральные формулы, позволяющие интерполировать в середине таблицы, используя близлежащие разности (Гаус, Стерлинг, Бессель)

3. Для неравноотстоящих узлов интерполирования существуют формулы Лагранжа, Ньютона.

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

5. Если существует возможность выбора узлов, то выбирают по условиям Чебышева, которое позволяет уменьшить погрешность аппроксимации.

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

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

, необходимо найти корни. Составляем таблицу по формуле, а затем задаваясь значением => ищат .

Оценка погрешности интерполяционной формулы Лагранжа

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

- абсолютная погрешность интерполяционной формулы Лагранжа (остаточный член)

Пример: с какой точностью можно вычислить с помощью ИФЛ для функции

Выбрав узлы интерполирования

, ,

ð

Лекция N 6 и 7

ПРИБЛИЖЕННОЕ РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ И ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ.

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

Пусть дано уравнение:

f(x)= 0,

Считается, что на отрезке [ a,b ] f(x) -везде определена и непрерывна. В некоторых случаях требования ужесточаются, а именно требуется существование и непрерывность f '(x) и даже f ''(x).

E- называется корнем уравнения, или корнем f(x), если выполняется условие:

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

1) определение корней - т.е. выделение отрезков и [ a,b ], содержащих один корень;

2) уточнение приближенных корней - т.е. доведение их до заданной точности.

ОПРЕДЕЛЕНИЕ КОРНЕЙ

Графический способ.

Выделяем три отрезка

В сомнительных случаях графическое определение корней необходимо подкрепить вычислениями.

Аналитический способ.

1) если функция f(x) концах отрезка принимает значения разных знаков на отрезке есть хотя бы один корень (теорема о наличии корня);

2) если функция на отрезке строго монотонна, то корень единственный (математически это означает, что f'(x) существует и имеет постоянный знак).

Пример:

на отрезке

	+	-
	-	-
	-
	+	+

на отрезке существует корень.

ГРАФИЧЕСКОЕ РЕШЕНИЕ УРАВНЕНИЙ.

Графически корни уравнения f(x)= 0, определяются, как абсциссы точек пересечения графика с осью ОX.

На практике часто бывает удобно уравнение f(x) заменить на равносильное уравнение:

(x) = (x),

где функции (x) и (x) более простые.

Тогда построив графики (x) и (x), искомые корни определяются, как абсциссы точек пересечения графиков.

Пример:

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ.

Пусть дано уравнение:

f(x)= 0 и имеет единственный корень.

Делится отрезок [ a,b ] пополам.

1) f(с)= 0, где с - корень уравнения

2) f(с) 0

Выбирается тот участок, где f(x) меняет знаки на концах, т.е. или . Отрезок делится пополам и т.д. В результате на каком-то участке получаем точный корень.

Признак разных знаков f(a) f(b)< 0

Признак одинаковых знаков f(a) f(b)> 0

АЛГОРИТМ МЕТОДА

МЕТОД ПРОПОРЦИОНАЛЬНЫХ ЧАСТЕЙ (МЕТОД ХОРД)

Пусть дано f(x) 0, необходимо найти x при котором f(x)= 0, известен отрезок [ a,b ], на котором f(a)< 0, f(b)> 0

Метод заключается в том, что отрезок [ a,b ] делится не пополам, а в отношении: , это дает приближенное значение корня.

1)

где =

Далее применяя этот прием к тому отрезку [ a, ] или [ , b ], на концах которого f(x) имеет противоположные знаки, получим второе

2) [ a, ] или [ , b ] Допустим что [ , b ]

и т.д.

Геометрический способ пропорциональных частей эквивалентен замене кривой y=f(x) - хордой, проходящей через точки А[a, f(a)] и B[b, f(b)]

Y

B

X

A

1) неподвижен тот конец, для которого f(x) совпадает со знаком её второй производной f^’’(x);

2) последовательные приближения x_n лежат по ту сторону корня , где функция f(x) имеет знак, противоположный знаку её второй производной.

АЛГОРИТМ МЕТОДА

МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ)

Найти корень уравнения f(x) на отрезке [ a,b ], при этом f'(x) и f''(x) непрерывны на отрезке [ a,b ].

= -

Геометрически метод Ньютона эквивалентен замене дуги кривой y=f(x), касательной, проведенной, в некоторой точке кривой.

Y

B

B₁

a

X

A

Ставится задача определения начального значения , от которого зависит скорость сходимости алгоритма.

Y

a b c X

с [a,b] непрактичный метод

Выбирать надо так, чтобы выполнялось условие f(X )f ''(X )>0

Т.е. в качестве исходной точки выбирается тот конец интервала [ a,b ], которому соответствует ордината того же знака, что и знак f''(x)

МЕТОД ИТЕРАЦИЙ

(метод последовательных приближений)

Дано уравнение f(x)=0, заменим равносильным уравнением

(x)=x,

Это означает что решение уравнения (1) есть абсцисса точки пересечения графиков (x) и x

МЕТОД

Выбирается некое приближение ,получим точку по формуле

Затем подставляем и получаем

Повторяя этот процесс имеем последовательность чисел:

(1)

Если последовательность сходится, т.е. существует предел , то переходя к пределу в (1) предполагая непрерывной, найдём:

или

Таким образом является корнем.

И так до тех пор, покa <

Геометрическая интерпретация метода

Строим график y=x и (x)=y

Y

X

x₀ x₁ E=x₂

Каждый действительный корень является абсциссой точки пересечения

СХОДИМОСТЬ МЕТОДА ИТЕРАЦИЙ

Теорема N1

Если функция (X)-определена и дифференцируема на отрезке [ a,b ]. Тогда если существует правильная дробь q такая, что

q <1, для a<x<b,

то процесс итерации

x = (x ) сходится независимо от начального значения .

Условия теоремы гарантируют сходимость метода при любом выборе начального условия из [ a,b ], т.е. этот метод в условиях теоремы является самоисправляющим. От выбор зависит лишь объем вычислений.

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

Теорема N2.

Условие минимума: если функция (x) удовлетворяет условию, то метод сходится.

0 (1- )r

где <1

r=b-a

СХОДИМОСТЬ МЕТОДА

Если функция (x) удовлетворяет условию Лившица, то метод сходится.

Условие Лившица:

0

где <1, r=b-a

Лекция №8 и 9

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

Общая характеристика методов решения систем линейных уравнений

Методы решения систем линейных уравнений в основном делятся на две группы:

1. Точные методы - представляющие собой конечные алгоритмы для вычисления корней системы.

2. Итерационные методы - позволяющие получить корни системы уравнений с заданной точночтью путём бесконечных сходящихся процессов.

Введём следующие обозначения:

- матрица коэффициентов