Точные и приближенные числа, источники погрешностей, классификация погрешностей

Оглавление

 

 

ПРЕДИСЛОВИЕ.................................................	4
ЛЕКЦИЯ 1. Понятие погрешности решения систем алгебраических уравнений......................................................
1.1. Точные и приближенные числа, источники погрешностей, классификация погрешностей................................
1.2. Абсолютные и относительные погрешности....................
1.3. Понятие о системе линейных уравнений.......................
1.4. Матричные уравнения......................................
Лекция 2. Точные и приближенные методы решения систем линейных алгебраических уравнений (слау)
2.1. Формулы Крамера для решения системы линейных уравнений
2.2. Решение системы линейных уравнений методом последовательного исключения неизвестных (метод Гаусса)
Лекция 3. Приближенные методы решения слау
3.1. Понятие предела для векторов и матриц
3.2. Метод простой итерации
Условия сходимости итерационного процесса
3.4. Оценка погрешности приближенного процесса методом итерации
Лекция 4. Метод Зейделя
4.1. Условия сходимости процесса Зейделя
4.2. Оценка погрешности процесса Зейделя
4.3. Приведение системы линейных уравнений к виду, удобному для итераций
Лекция 5. Методы решения нелинейных уравнений
5.1. Итерационные методы решения нелинейных уравнений
5.2. Метод Рыбакова
5.3. Метод наискорейшего спуска
Лекция 6. Интерполирование и экстраполирование
6.1. Интерполяционный многочлен лагранжа
6.2. Оценка погрешности интерполяционного многочлена лагранжа
Лекция 7. Конечные разности
7.1. Первая интерполяционная формула ньютона для равноотстоящих узлов интерполяции
7.2. Вторая интерполяционная формула ньютона
7.3. Оценка погрешностей интерполяционных формул ньютона
Лекция 8. Линейное интерполирование
8.1. Интерполирование по Эйткину
8.2. Интерполяция и приближение сплайном
Лекция 9. Численное интегрирование функций
9.1. Постановка задачи
9.2. Формула прямоугольников
9.3. Формула трапеций.
9.4. Формула парабол (формула симпсона).
Лекция 10. Численные методы решения задачи коши для обыкновенных дифференциальных уравнений
10.1. Задача коши. Общие замечания. Постановка задачи
10.2. Метод Эйлера
10.3. Модифицированный метод Эйлера
10.4. Метод Рунге-Кутта
Лекция 11. Разностный метод решения уравнений математической физики (метод сеток)
11.1. Метод сеток для уравнения параболического типа
Лекция 12. Метод сеток для уравнения гиперболического типа
12.2. Метод сеток для уравнений пуассона и лапласа
Образцы выполнения контрольных работ
Контрольная работа № 5
Контрольная работа № 6
Контрольная работа №7
Контрольная работа №8
Примеры заданий для самостоятельной работы
Задание 1
Задание 2
Задание 3
Задание 4
Задание 5
Задание 6
Задание 7
Задание 8
Вопросы для самостоятельной подготовки
Библиографический список

 

ПРЕДИСЛОВИЕ

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

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

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

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

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

 

 

ЛЕКЦИЯ 1.  ПОНЯТИЕ ПОГРЕШНОСТИ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Источники погрешностей

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

2. Приближенные значения величин, входящих в условия задачи (погрешности исходных данных).

3. Замена бесконечных процессов, пределами которых являются искомые величины, конечной последовательностью действий.

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

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

 

Погрешности можно подразделить на три большие группы:

 

1. Исходные (или неустранимые) погрешности, к которым относятся погрешности, возникающие в результате приближенного описания реальных процессов и неточного задания исходных данных. Эти погрешности проходят через все вычисления и являются неустранимыми.

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

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

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

 

При работе с приближенными величинами, вычислитель должен уметь:

 

- давать математические характеристики точности приближенных величин;

- зная степень точности исходных данных, оценивать степень точности результатов;

- брать исходные данные с такой степенью точности, чтобы обеспечить заданную точность результата;

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

 

Матричные уравнения

Рассмотрим три вида матричных уравнений.

1. Уравнение вида . Умножим обе части уравнения на слева:

 , где  .                        (1.7)

 

Пример:         или  .

Находим обратную матрицу  .  - детерминант матрицы A.

 - алгебраическое дополнение к матрице A.

 

 ;  .

 

 

     2. Матричное уравнение вида:

                                                  (1.8)

 

Умножим обе части уравнения на справа.

 

Пример: Решить матричное уравнение

 .

Решение:

 ~ ;  ;

 ;  ;  ;

 ;  ;  ;

 ;  ;  ;

 ;  ;

Матричное уравнение  третьего вида:

.                                                 (1.9)

Для его решения умножим обе части уравнения слева на , а справа на , тогда получим

;

.

Пример: Решить матричное уравнение

 

 .

Решение:

 ;  ;  ;

 

 ;  ;  ;

 

.

 

Находим сначала , а затем и искомое решение матричного уравнения

; ; ;

 .

ЛЕКЦИЯ 2. ТОЧНЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (СЛАУ)

СЛАУ допускают как точные, так и приближенные методы решения.

 К точным относятся метод Крамера, метод Гаусса и метод обратной матрицы.

К приближенным методам относятся: метод простой итерации, метод последовательных приближений и метод Зейделя.

Пусть дана система

 

                          (2.4)

 

Будем исключать неизвестное x ₁ из всех уравнений системы (2.4), кроме первого. Назовем x ₁ – ведущим неизвестным, а коэффициент a ₁₁ – ведущим коэффициентом. Разделив первое уравнение на a ₁₁ (это возможно если a ₁₁ ¹ 0), получим:

 

 .

Обозначим

 

; ; ;  ;

и вообще

 

, (j > 0),

тогда

 

или

 

.                                  (2.5)

 

Дальнейшее решение системы уравнений (2.4) методом Гаусса представляет собой ряд последовательных шагов:

1. Для исключения неизвестного вычтем из второго уравнения системы (2.4) уравнение (2.5), умноженное на a ₂₁:

 

−

___________________________________________________________

     

Обозначим

 

.

 

Перепишем полученное уравнение в виде

 

 .

 

2. Из третьего уравнения системы (2.4) вычтем уравнение (2.5) умноженное на

–

________________________________________________________

     

 

Обозначим

.

 

Перепишем полученное уравнение в виде

 

 .

 

3. Из четвертого уравнения системы (2.4) вычитаем уравнение (2.5), умноженное на . Применив аналогичные преобразования, получим следующее уравнение:

 ,

 

где

 .

 

В результате элементарных преобразований имеем систему 3-х уравнений с тремя неизвестными, эквивалентную системе (2.4):

 

                                (2.6)

 ,

 

где коэффициент                вычисляется по формуле   

     

 .

 

Разделив далее коэффициент первого уравнения системы (2.4)  на ведущий коэффициент , получим первое уравнение системы в виде:

 

 ,

 

обозначим , где j > 2, тогда первое уравнение системы (2.4)  примет вид:

 

или

 

 .

 

Исключая теперь  из всех уравнений системы (2.4), кроме первого, мы получим систему двух уравнений с двумя неизвестными:

 

,                                    (2.7)

 

где  ,  .

Разделив коэффициенты первого уравнения системы (2.7) на ведущий коэффициент и ведущий коэффициент     получим

 

,                                          (2.8)

где    , j > 3, то есть  .

 

Исключив теперь х ₃, аналогичным путем из системы (2.8), находим:

 

 ,                                              (2.9)

где

 

, ;

отсюда

 

.                                              (2.10)

 

Остальные неизвестные системы последовательно определяются из уравнений (2.5, 2.8, 2.9, 2.10):

 

;

;

;

 .

 

Таким образом, процесс решения системы линейных уравнений по методу Гаусса сводится к построению эквивалентной системы уравнений (2.5, 2.8, 2.9, 2.10, …).

Метод Гаусса применим при условии, что все ведущие коэффициенты отличны от нуля.

Для удовлетворения данных условий вычисления проводятся по схеме единственного деления.

 

 

ЛЕКЦИЯ 3. ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ

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

Эффективность применения приближенных методов зависит от удачного выбора начального вектора и быстроты сходимости процесса. Мы рассмотрим два метода - метод последовательных приближений и метод Зейделя.

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

 

Пусть дана система линейных уравнений:

 

.                            (3.3)

 

 

В матричном виде:

 

 ,

; ;    .                       (3.4)

 

Предполагая, что диагональные элементы a_ii ¹ 0,(j = 1, 2, …, n), выразим х ₁ через первое уравнение системы, х ₂ – через второе, и т.д.

 

;

;

…                                                   (3.5)

.

 

Обозначим  , ,  где i = 1, …, n; j = 1, …, n, тогда

                            (3.6)

 

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

 

Введя обозначения

,  .

Запишем систему (3.3) в матричной форме  

или

 .                   (3.7)

 

Решим систему (3.7) методом последовательного приближения, за нулевое приближение возьмем столбец свободных членов:

 

- нулевое приближение;

 

- 1-е приближение;

 

- 2-е приближение.

 

Любое приближение вычисляется по формуле X ^{( k + 1)} = b + a Х ^{( k )}. Если последовательность приближения X ⁽⁰⁾, X ⁽¹⁾, …, X ^{( k )} имеет предел X  = lim X ^{( k )}  при k ¥, то этот предел является решением системы (3.6). Поскольку по свойству предела lim X ^{( k +1)} = b + a lim X ^{( k )}, k ¥, тогда X = a + b Х.

Пусть дана линейная система

                           (4.1)

Выбираем произвольно начальное приближение корней  и подставляем в первое уравнение системы (4.1)

 ,

полученное первое приближение подставляем во второе:

.

Полученные первые приближения х ₁⁽¹⁾ и х ₂⁽¹⁾ подставляем в третье уравнение системы (4.1)

и т. д.

.

Аналогично строим вторые и третьи итерации.

Таким образом, предполагая, что k приближение корней х ^k _i  известно, по методу Зейделя строим (k + 1) приближение

где k = 0, 1, 2, …, n.

 

 

Пример. Методом Зейделя решим систему:

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

2. За нулевые значения возьмем соответствующие значения свободных членов

.

3. Строим итерации по методу Зейделя

 

Второе приближение

 

И т.д.

 

№ итерации
0	0,19	0,97	-0,14
1	0,2207	1,0703	-0,1915
2	0,2354	1,0988	-0,2118
3	0,2424	1,1088	-0,2196
4	0,2454	1,1124	-0,2226
5	0,2467	1,1138	-0,2237
6	0,2472	1,1143	-0,2241
7	0,2474	1,1145	-0,2243
8	0,2475	1,1145	-0,2243

 

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

 

;

 

Процесс Зейделя для линейной системы Х = b + a Х также, так и процесс последовательных приближений, сходится к единственному решению при любом выборе начального приближения, если какая-нибудь из норм матрицы a меньше единицы. То есть

либо

,

либо

.

 

Процесс Зейделя сходится к единственному решению быстрее процесса простой итерации.

 

 

Рис. 5.1

 

 

 

Рис. 5.2

имеет вид

 .

Найдем   х = х _1, для которого   y = 0

 .

Рис. 5.3

 ,

 ,

...

 .

 

Неподвижными концами отрезка является тот, для которого знак функции совпадает со знаком второй производной .

 

г). Метод Ньютона.

Пусть корень уравнения f (x) = 0 отделен на отрезке [ a, b ], причем  и   непрерывны и сохраняют постоянные значения на всем отрезке        [ a, b ].

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

 

 

Первый случай (рис.5.4):

 

f (a) < 0, f (b) > 0, > 0, > 0(основная линия)

или

f (a) > 0, f (b) < 0, < 0, < 0(пунктирная линия).

Рис. 5.4

 

 

Проведем касательную к кривой y = f (x)  в точке B ₀

 

 .

Полагая y = 0, x = x _{1 ,} получим

 _,

 

 ,

...

 

 ^.

Второй случай (рис. 5.5):

 

f (a) < 0, f (b) > 0, > 0, < 0(основная линия)

 

или

f (a) > 0, f (b) < 0, < 0, > 0(пунктирная линия),

 

.

 

 

 

Рис. 5.5

 

Полагая y = 0, х = х ₁, получим

 _,  ,...,  ^.

 

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

 , a = x _{0 .}

д). Модифицированный метод Ньютона.

Заключается в том, что вместо вычисления производной   на каждом шаге итераций находится ее приближенное значение

 

 ,  .

 

Следовательно, итерационная формула имеет вид

 

 .

 

Значение  не обязательно должно быть постоянно. Равенство  позволяет уменьшить число исходных данных при вводе.

 

Метод Рыбакова

Можно рассматривать этот метод как модификацию метода Ньютона. При замене  некоторым числом , где  – значение х на [ a, b ], при котором производная максимальна.

При  сходимость не нарушается, но замедляется.

Метод Рыбакова удобен для поиска всех корней уравнения f (x) = 0 на [ a, b ].

1. Задаем начальные значения х = х ₀ = а.

2. Для каждой последовательной итерации (n = 0, 1, 2, …) вычисляем

и проверяем условие x_n < b, если оно выполняется, то, значит, найдены все корни, в противном случае проверяем выполнение условия . Если оно не выполняется, то повторяем цикл с пункта 2  и переходим к пункту 3.

3. Задаем начальное приближение     и снова идем на пункт 2.

Метод наискорейшего спуска

 

 

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

 .

Приведенное описание не определяет алгоритм однозначно, т.к. ничего не сказано о выборе параметра  . Его можно определять из условия минимума величины  .

В этом случае рассматриваемый метод называют методом наискорейшего градиентного спуска.

Для функции , соответствующей системе линейных уравнений с матрицей , задача нахождения минимума решается в явном виде

так как

и

 .

Обозначим  через  , т.е.

 

 .

 

Предположим, что  . Учитывая, что , вычислим   :

 

 

 

 

 

 

,

 

 

 .

 

 

ЛЕКЦИЯ 6. ИНТЕРПОЛИРОВАНИЕ И ЭКСТРАПОЛИРОВАНИЕ

 

1. Математическая постановка задачи интерполирования.

В экономике и технике, часто приходится сталкиватьcя с необходимостью вычисления значений функции у = f (х) в точках, отличных от значения аргумента, фиксированных в таблице.

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

Пусть на отрезке [ a, b ]  задана функция у = f (х) своими n + 1 значениями ; ; …;  в точках x ₀, x ₁, …, x_{n ,}  которые назовем узлами интерполяции.

Требуется найти аналитическое выражение табулированной функции F (х), совпадающее в узлах интерполяции со значениями заданной функции,

 

y 0	y 1	…	yn- 1	yn
x 0	x 1	…	xn - 1	xn

 

т.е.

; ; …; .

 

Процесс вычисления значений функций в точках х, отличных от узлов интерполяции, называется интерполированием функции f (х).

Если аргумент х находится за пределами отрезка интерполирования     [ x ₀, x_n ], то задача определения значения функции в точке х называется экстраполированием.

Задача становится однозначной, если в качестве интерполирующей функции f (х) для функции у = f (х), заданной своими n + 1 значениями, выбрать многочлен F_n (x) степени не выше n, такой, что

 

; ; …;  .

Многочлен F_n (x) удовлетворяющий этим условиям, называют интерполяционным многочленом, а соответствующие формулы – интерполяционными.

В случае, когда F (x) выбирается в классе степенных функций, интерполяция называется параболической.

 

При интерполировании возникает ряд задач:

 

1. Выбор наиболее удобного способа построения интерполяционной функции для каждого конкретного случая.

2. Оценка погрешности при замене f (x) интерполирующей функцией F (x) на отрезке [ a, b ].

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

Окончательно получаем

 

 .

 

Этот многочлен называется интерполяционным многочленом Лагранжа

 

 ,

 

где х ₀, х ₁,…. х _n – узлы интерполяции, а х – значение аргумента, для которого определяется приближенное значение по интерполяционной формуле Лагранжа.

Обозначим произведение элементов первой строки через R ₀:

.

 

В общем виде произведение элементов i строки

 

 .

 

Дополнительно вычислим произведение элементов, расположенных на главной диагонали

 ,

тогда интерполяционный многочлен Лагранжа можно переписать в виде

 

 .

Интерполяционная формула Лагранжа заметно упрощается, если узлы интерполяции равноотстоящие, т.е.  .

Обозначим q = (x - x ₀ )/ h, тогда

 

 .

Введем обозначения:

…

 ,

тогда

 .

 

Интерполирование по Эйткину

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

Пусть некоторый интерполяционный многочлен F (x) степени n принимает в узлах интерполяции х ₀, х ₁, …, х _n значения

 

 

; ; …;   .

 

 

Воспользовавшись формулой Лагранжа для случая линейной интерполяции, на отрезке [ x ₀, x ₁] интерполяционное значение функции можно вычислить по формуле

 

,                     (8.1)

 

на отрезке [ x ₁, x ₂]

 

     ,                  (8.2)

 

 

и, наконец, на отрезке [ x ₀, x ₂] по формуле

 

     .                 (8.3)

 

Далее заменим у ₀ и у ₂ в формуле (8.3) соответственно на F _{0, 1}(x) и F _{1, 2}(x).

 

Получим следующее выражение