Численные методы. 1-2Численные методы. Прикладные компьютерные программы основные понятия

• Название: Прикладные компьютерные программы основные понятия
• Анкор: Численные методы
• Дата: 15.11.2021
• Размер: 1.25 Mb.
• Имя файла: 1-2Численные методы.ppt
• Тип: Решение; #272962

Прикладные компьютерные программы

ОСНОВНЫЕ ПОНЯТИЯ

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

Все численные методы делятся на точные и приближенные методы

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

Источники и классификация погрешностей

Ошибки появляются за счет:
1) неточностей в исходных данных. Данная погрешность является неустранимой, и возникает за счет округления или при использовании экспериментальных данных.
2) использования итерационных методов для получения результата, где теоретически можно получить точное решение, совершая бесконечное число шагов вычислений. Так как число шагов ограничено искусственно, то в вычисления вносится погрешность.
3) погрешностей самих методов.

Классификация погрешностей

1) погрешность задачи – погрешности, возникающие при постановке математической задачи.
2) погрешность метода – это погрешность, возникающая при замене точной задачи на задачу близкую по результату.
3) остаточная погрешность - связана с наличием бесконечных процессов в математическом анализе.

Классификация погрешностей

4) начальная погрешность – это погрешность, связанная с наличием в формулах числовых параметров, значения которых определены приближенно.
5) погрешность округления – это погрешность, связанная с системой счисления. Например,
6) погрешность действий – это погрешность, связанная с действиями над приближенными числами.

Основные понятия и определения теории погрешностей

Обозначим через A, B, C,…,U,…- точные числа; a, b, c,…,u,.. - приближенные значения.
Определение 1
Приближенным числом a называется число, незначительно отличающееся от точного числа A и замечающее число A в вычислениях.

Если a>A ,то a называется приближенным числом с избытком.
Если a ,то a - приближенное число с недостатком.

Определение 2
Пусть a - приближенное значение некоторой величины, A - точное значение, тогда абсолютной погрешностью приближенной величины называется абсолютная величина разности между a и A и , т.е.
Абсолютная погрешность является не полной характеристикой приближенной величины.


Определение 3
Относительной погрешностью приближенного числа a называется отношение абсолютной погрешности этого числа к модулю точного числа A:


Так как точное значение приближенной величины, как правило, неизвестно, то вводится понятие предельной абсолютной погрешности.
Определение 4
Предельной абсолютной погрешностью называется число, удовлетворяющее неравенству:


Определение 5
Предельной относительной погрешностью приближенного числа a, называют всякое число, не меньше относительной погрешности этого числа:

Значащая и верная цифра приближенной величины

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


Определение 7 (первое определение верной цифры)
Верной цифрой приближенной величины называется такая цифра, если абсолютная погрешность не превосходит единицы разряда этой цифры.
Например, a=53.1412,
53.14 - верные цифры.
Приближенные числа принято записывать так, чтобы они содержали только верные цифры. В технических таблицах допускается одна сомнительная цифра. Во всех математических таблицах содержатся только верные цифры, соответствующие второму более строгому определению верной цифры.


Определение 8 (второе определение верной цифры)
Если абсолютная погрешность приближенного числа a не превышает половины единицы разряда, выражаемого n-ой значащей цифрой (считая слева направо), то говорят, что первых n значащих цифр приближенного числа a являются верными.


Любое положительное число может быть представлено в виде
Если , то являются верными.


Пример 1:

Округление чисел

Чтобы округлить приближенное число a до n значащих цифр, отбрасывают все цифры, стоящие справа от n -ой значащей цифры, или, если нужно для сохранения разрядов, заменяют их нулями. При этом, если первая из отброшенных цифр:
1) меньше 5, то оставшиеся десятичные знаки сохраняются без изменения;
2) больше 5, то к последней оставшейся цифре прибавляется единица;
3) равна 5 и среди остальных отброшенных есть неравные нулю, то последняя оставшаяся цифра увеличивается на единицу;
4) равна 5 и все остальные отброшенные цифры равны нулю, то последняя оставшаяся цифра остается неизменной, если она четная, и увеличивается на единицу, если она нечетная (правило четной цифры).

Округление чисел

Пример :
 = 3,14159266535
N=3, a=3.14
N=4, a=3.142
N=6, a=3.14159

Округление чисел

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

Округление чисел

Следствие.
За предельную относительную погрешность числа a можно принять:
где - первая значащая цифра числа a.

Погрешность алгебраической суммы

Теорема 2. Абсолютная погрешность алгебраической суммы нескольких приближенных чисел не превышает суммы абсолютных погрешностей этих чисел.
Доказательство:
Пусть - приближенные числа.
Рассмотрим их алгебраическую сумму
Очевидно, что
Следовательно
Следствие. За предельную абсолютную погрешность алгебраической суммы принимают сумму предельных абсолютных погрешностей слагаемых.

Погрешность произведения и частного

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


При умножении приближенного числа a на точный множитель k предельная относительная погрешность не изменяется, а предельная абсолютная погрешность увеличивается в модуль k – раз.
Пусть
Тогда


Теорема: Относительная погрешность частного не превышает суммы относительных погрешностей делимого и делителя, т.е.
Следствие. Если , то предельная относительная погрешность частного равна сумме предельных относительных погрешностей делимого и делителя .

Погрешность степени

Теорема: Предельная относительная погрешность k– той степени числа x в k раз больше предельной относительной погрешности самого этого числа.

Погрешность корня

Теорема: Предельная относительная погрешность корня k – той степени числа x в k – раз меньше предельной относительной погрешности самого числа x.

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

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

Приближенное нахождение изолированных корней уравнения f(x)=0 состоит из 2-х этапов:

1) Отделение корней
2) Уточнение корня до заданной степени точности


Отделить корни, это значит установить такие промежутки [α, β] (a, b), внутри которых содержится по одному единственному корню уравнения (1).
Отделение корня во многих случаях удается провести с помощью графического метода решения уравнения. С этой целью строим график функции y=f(x) и находим промежутки [a, b], внутри которых находится абсцисса точки пересечения графика функции y=f(x) с осью Ох, т.е. нуль функции f.


Отделение корней

Пример 1: Отделить все корни уравнения

Решение:


Графический метод


Решение:
Заменим уравнение на равносильное ему:


y=2-x2


y=ex


Пример 2: Отделить все корни уравнения


Графический метод

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

Теорема.
Непрерывная функция, принимающая на концах сегмента [a, b] значения разных знаков, достигает значения ноль, хотя бы в одной точке интервала [a, b].
Воспользоваться приведенной теоремой можно следующим образом:
Возьмем конечный промежуток [A, B] в котором мы подозреваем существование корней и разделим его на n равных частей точками А=а0<а1<…<аn=В.
Последовательно, на каждом сегменте [аk-1, аk], проверяем значение функции: если при некотором значении k=i получим f(аi-1)*f(аi)<0, то сегмент [аi-1, аi] содержит корень уравнения f(x) = 0.
Чтобы удостоверится в единственности корня на этом промежутке, достаточно убедиться, что производная функции f´(х), сохраняет постоянный знак на этом сегменте.

Алгоритм метода:

Шаг 1. Задаются концы интервала А, В (обычно от -50 до 50) и число точек деления n (не менее 100)
Шаг 2. Находят расстояние между точками: h=(В-А)/n
Шаг 3 . За начальную точку выбирают точку х = А
Шаг 4. Вычисляют значение функции f(х)
Шаг 5. Находят второй конец отрезка: y=x+h и вычисляют значение функции f(y)
Шаг 6. Проверяют условие: f(х)· f(y)<0.
Если условие выполняется, переходят к шагу 7, в противном случае х:=х+h и переходят к шагу 4.
Шаг 7. Вывод х, y.


_


_


+


-


+


Н


А, В, n


h:=(В-А)/n


x:=А


S:=0


f(х)*f(х+h)<0


S:=S+1


[х; х+h]


x:=х+h


х>B


+


S=0


На промежутке [A,B] корней нет


К

МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ

Пусть необходимо найти изолированные корни уравнения f(х)=0 на сегменте [a, b].
Пусть на интервале [a, b] существует только один корень и на нем функция f(х) определена в любой точке.
Тогда выполняется условие f(а)·f(b)<0, т.е. на концах интервала функция f(х) имеет разные знаки.
На этом свойстве и основан наиболее простой способ уточнения корня - метод, называемый методом деления отрезка пополам.


Пусть наш корень х требуется найти с предельной абсолютной погрешностью ε, тогда для достижения указанной точности достаточно добиться того, чтобы
bn-an <2·ε и за приближенное значение корня возьмем

Алгоритм метода деления отрезка пополам

Шаг 1. Задаются концы интервала a и b, точность метода 
Шаг 2. За начальную точку выбирается точка а
Шаг 3. Вычисляется значение функции f(а)
Шаг 4. Находится середина отрезка [a, b]: х=(a+b)/2.
Шаг 5. Вычисляется значение функции f(х).
Шаг 6. Определяется новый интервал, на котором есть корень из условия f(а) f(х)<0. Если условие верно, то необходимо сделать присвоение b:=x, в противном случае делается присвоение а:=х.
Шаг 7. Проверяется условие b – a  . Если условие верно, управление передаётся шагу 8, в противном случае - шагу 3.
Шаг 8. Вывод х и f(x).

Блок-схема метода деления отрезка пополам

Пример.

Методом деления отрезка пополам решить уравнение f(x)=х2+2х-4,8=0
на интервале [1; 2] с точностью  = 0,2.
Решение.
Убедимся, что на данном интервале существует корень:
f(1)f(2)=-1,83,2=-5,76<0, т.е. корень существует.
х1=(1+2)/2 = 1,5; f(x1)=f(1,5)=1,45
f(1)=-1,8; f(1)f(1,5)=-1,81,45=-2,61<0, т.е. корень на отрезке [1; 1,5]
1,5-1=0,5>
Тогда х2 =(1+1,5)/2 = 1,25; f(x2)=f(1,25)=-0,74
f(1)f(1,25)=-1,8(-0,74)=1,33>0, т.е. корень на отрезке [1,25; 1,5].
1,5-1,25=0,25>
х3=(1,25+1,5)/2 = 1,375; f(x3)=f(1,375)=-0,15;
f(1,25)=-0,74; f(1,25)f(1,375)=-0,74(-0,15)=0,11.
Следовательно, корень расположен на отрезке [1,375; 1,5].
1,5-1,375=0,125<. Т.е. искомое решение х = 1,375.

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

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

Формула для уточнения корня

Запишем уравнение касательной в точке х0=b: у=f(x0)+ (x0)(x-x0).
Уточнённое решение будет в точке пересечения касательной и оси абсцисс, т.е. у = 0.
Тогда: f(x0)+ (x0)(x-x0)=0 или f(x0)+ (x0)x- (x0)x0 = 0.
Пусть х1=х
Тогда . Следовательно, и т.д.
Т.е. формула уточнённого корня примет вид:

Для выбора точки, в которой будет проводиться первая касательная, следует использовать одно из двух условий:

начальной точкой выбирают тот конец отрезка, для которого выполняется условие:
если выполняется условие то начальной точкой выбирают точку а, в противном случае –точку b.

Алгоритм метода Ньютона (касательных)

Шаг 1. Задаются концы отрезка, т.е. числа a и b; задаётся точность .
Шаг 2. Выбирается начальная точка из условия .
Если условие верно, то начальная точка - это точка а, в противном случае - точка b.
Шаг 3. Определяется уточнённое значение корня по формуле:
Шаг 4. Проверяется условие .
Если условие верно, то управление передается шагу 5, в противном случае управление передаётся шагу 3, используя при этом новые данные.
Шаг 5. Вывод xn, f(xn).


Блок – схема метода:


Н


a, b, ε


x = b


x = a


х = у


К


у, f(y)

Пример.

Методом Ньютона решить уравнение f(х) = х2 + 2х - 4,8 = 0
на интервале [1, 2] с точностью ε = 0,2.
Решение:
FI(х) = 2х+2.
Проверяем условие , т.е.
Следовательно, за начальную точку выбираем х0=1.
Тогда
Определяем следующую точку:
Следовательно, искомое решение х = 1,41.

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

Пусть необходимо решить уравнение f(х)=0 на интервале [a, b] с точностью ε.
Уравнение f(х)=0 некоторым образом преобразуется к равносильному уравнению х=φ(х) (*) имеющему корень t, на отрезке [a, b]. Функция φ предполагается непрерывной на этом отрезке.
При этом, чтобы метод сходился, необходимо выполнение условия: |φ'(х)|<1, для любых х из интервала [a, b]. Чем меньше это значение (φ'(х)), тем быстрее сходится метод.
Поэтому, обычно за начальное приближение выбирают тот конец интервала, в котором меньше абсолютное значение производной.
Суть метода в том, что для значения хi-1 вычисляется функция φ(хi-1) и приравнивается к хi. Этот процесс выполняется до тех пор, пока не выполнится условие |хi - хi-1| ≤ ε.

Алгоритм метода итераций

Шаг 1. Задаются концы отрезка а и b , точность метода ε.
Шаг 2. Выбирается начальное приближение из условия φI(a)< φI(b).
Если условие верно, то начальной точкой выбирают точку а, в противном случае - точку b.
Шаг 3. Вычисляется новое приближение по формуле xn = φ(xn-1).
Шаг 4. Проверяется условие Ixn-xn-1I≤ε.
Если условие верно, то управление передается шагу 5, в противном случае управление передается шагу 3, используя только что полученное приближение.
Шаг 5. Вывод хn и f(xn).

Пример.

Решить уравнение с точностью ε = 0,01, уточняя корень методом итераций.
Решение:
1) Для отделения корня построим график функции:

Х	х2 - cos(x)
-5	0,283662
-4	-0,65364
-3	-0,98999
-2	-0,41615
-1	0,540302
0	1
1	0,540302
2	-0,41615
3	-0,98999
4	-0,65364
5	0,283662

За отрезок отделения возьмем [0, 1].
2) Уточним корень. Запишем уравнение в виде (*)
3) Проверим условие : все значения условие выполняется.
4) , тогда и отсюда следует что для всех х € [0, 1] производная .
5) Кроме того, , поэтому за начальную точку берем х0 = 0, подставим это значение в (*) и найдем
=1, затем =0,735
Аналогично х3=0,8613, х4=0,8613, х5=0,8071, х6=0,8317, х7=0,8207, х8=0,8257
, т.е. за корень х можно взять 0,8257.


Блок - схема метода итераций


Н


a, b, ε


x = b


x = a


х = у


К


у = φ(x)


у, f(y)

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

Строятся две линии:
y=x (биссектриса угла х0y) и y=φ(х) — некоторая кривая. Пересечение этих линий и есть корень уравнения f(х)=0


y=φ(x)


y=x


х0


х1


х2


х


t


y

Искусственный прием

Если найденное каким-либо способом φ(х) не удовлетворяет условию |φ'(х)|<1, то прибегают к следующему приему:
Умножаем обе части уравнения f(х)=0 на α и прибавляем х.
Получим:
φ(х)
где , , .