Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Понятие о численных методах

Вычислительные (численные) методы — методы решения математических задач в численном виде

Представление как исходных данных в задаче, так и её решения — в виде числа или набора чисел

В системе подготовки инженеров технических специальностей является важной составляющей.

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

3.Метод деления отрезка пополам. Пусть дано уравнение f(x)=0, функция f(x) непрерывна на интервале [a,b]. Условие f(a) f(b)<0 указывает тогда на наличие хотя бы одного корня на этом отрезке.

Поделим отрезок [a,b] пополам точкой c, координата которой c=(a+b)/2 и вычислим значение функции f(c).

Возможны два случая:

а) f(a) f(c)>0, т.е. значения функции на концах отрезка [a, c] одинаковы по знаку; тогда корень уравнения находится на отрезке [c, b] и отрезок [a, c] можно исключить из дальнейшего рассмотрения, перенеся точку a в точку c: a=c; f(a)=f(c) (рис. а);

б) f(a) f(c)<0, т.е. значение функции на концах отрезка [a, c] противоположны по знаку; тогда корень находится на отрезке [a, c] и отрезок [c, b] можно исключить из дальнейшего рассмотрения, перенеся точку b в точку c: b=c (рис. б).

После исключения правой или левой половины отрезка продолжают деление пополам до тех пор, пока длина оставшегося интервала [a, b] не станет меньше некоторой заданной малой величины , т.е.  b-a <, и тогда любое значение аргумента из отрезка [a, b] можно считать корнем с погрешностью . Обычно принимают в качестве корня середину отрезка.

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

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

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

Удобно оформить алгоритм метода в форме процедуры, тогда имя функции, вычисляющей f(x), можно передать в эту процедуру через список параметров. Отметим, что согласно требованиям Turbo Pascal для функции или процедур, имена которых являются аргументами других процедур или функций, описывается соответствующий процедурный тип. В приводимой ниже процедуре mpd, реализующей метод деления отрезка пополам, процедурный тип для функции имеет описание:

Type

mpd_func=function (x:real):real;

Все пояснения к тексту процедуры приведены в виде комментариев. Процедура включена в библиотеку Mathlib.

Procedure MPD (var x: real; {искомый корень}

a, b, {нижняя и верхняя границы интервала}

e: real; {допустимая абсолютная погрешность}

F: mpd_func); {имя функции, вычисляющей f(x)}

var

fa, fb, fc, c: real;

begin

{Вычисление функции на границах интервала и проверка,

не является ли граница корнем}

fa:= F(a); if fa = 0.0 then begin x:= a; exit end;

fb:= F(b); if fb = 0.0 then begin x:= b; exit end;

{Проверка наличия корня на интервале [a,b]}

if (fa*fb) > 0.0 then begin

writeln;

writeln(' MPD: Нет коpней на интеpвале [ ',a);

writeln(' ',b,' ]');

writeln(' f(a) = ',fa);

writeln(' f(b) = ',fb);

halt;

end;

{Деление отрезка и исключение половины,

не содержащей корня}

repeat

c:= (a+b)/2.0;

fc:= F(c);

if fa*fc < 0.0 then b:= c

else

begin

a:= c; fa:= fc

end;

until ABS(a-b) < e; {Условие окончания счета}

x:= (a+b)/2.; {Корень - середина отрезка}

end; { MPD }

Таким образом, для решения алгебраического или трансцендентного уравнения методом деления отрезка пополам можно воспользоваться типовой процедурой mpd библиотеки Mathlib.

Вызов процедуры осуществляется оператором

mpd (x,a,b,e,f);

где x – искомый корень; a и b – исходные верхняя и нижняя границы интервала поиска корня; e – допустимая абсолютная погрешность; f – имя функции, вычисляющей выражение f(x). Согласно заголовку процедуры, все скалярные величины имеют тип real.

В библиотеке Mathlib имеется еще одна процедура, реализующая метод деления отрезка пополам, особенность которой – сканирование всего отрезка [a, b] с некоторым заданным шагом  x для предварительного отделения корня. Эту процедуру удобно использовать, если заранее трудно локализовать корень.

Вызов процедуры

mpd_scan(x,a,b,delta,eps,fct);

где x – искомый корень; a, b – нижняя и верхняя границы поиска корня; delta – шаг сканирования; eps – допустимая абсолютная погрешность; fct –имя внешней функции, вычисляющей выражение f(x). Все скалярные величины типа real.

4.Решение НУ. Метод итераций. Одним из наиболее важных способов численного решения уравнений является метод итерации. Сущность этого метода заключается в следующем. Пусть дано уравнение

где f(x) – непрерывная функция, и требуется определить его вещественные корни. Заменим уравнение (1) равносильным уравнением

Выберем каким-либо способом грубо приближенное значение корня x₀ и подставим его в правую часть уравнения (2). Тогда получим некоторое число

Подставляя теперь в правую часть равенства (3) вместо x₀ число x₁ получим новое число x₂=j (x₁). Повторяя этот процесс, будем иметь последовательность чисел

Если эта последовательность – сходящаяся, т.е. существует предел , то, переходя к пределу в равенстве (4) и предполагая функцию j (x) непрерывной, найдем:

или

x =j (x). (5)

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

Доказано, что достаточными условиями сходимости итерационного процесса является выполнение условия | j (x)<1 для xО [a,,b].

При этом процесс сходится к единственному корню x.

На рис. 1 приведен пример сходящегося итерационного процесса x_n+1=j (x_n) при 0<j ’(x)<1 и на рис.2 – расходящегося при j ’(x)