Численные методы
fi = fi - aikyk ; k=1,m . (16)
![]()
![]()
Коефіціенти cij і праві частини yi ; i=1,m ; j=i+1,m зберігаються у пам’яті ЕОМ і використовуються при здійсненні зворотнього ходу за формулами (10).
Основним
обмеженням
методу є припущення,
що усі елементи
,
на які здійснюється
ділення, відрізняються
від нуля. Число
називається
провідним
елементом на
К-му
кроці вилучення.
Навіть,
якщо деякий
провідний
елемент не
дорівнює нулеві,
а просто є близьким
до нуля, в процесі
обчислень може
мати місце
нагромадження
похибок. Вихід
з цієї ситуації
полягає в тому,
шо як провідний
елемент вибирається
не
, а інше число
( тобто на
К-му
кроці вилучається
не xk,
а інша змінна
xj
,
)
.
Така
стратегія
вибору провідних
елементів
здійснюється
в методі Гаусса
з
вибором
головного
елементу, який
буде розглянуто
пізніш.
А тепер підрахуємо число арифметичних дій, що необхідні для розв’язання системи за допомогою методу Гаусса. Оскільки виконання операцій множення і ділення на ЕОМ потребує набагато більше часу, ніж виконання додавання і віднімання, обмежимось підрахуванням числа множень і ділень.
1.Обчислення
коефіцієнтів
за формулами
(13) потребує:
(m-k)=1+2+...+(m-1)=
ділень
.
2.Обчислення
усіх коефіцієнтів
за формулами
(14) потребує
множень
(тут ми використовуємо
легко перевіряєму
за індукцією
рівність
).
Таким
чином, обчислення
ненульових
елементів
трикутної
матриці С потребує

операцій множення і ділення.
3.Обчислення правих частин yk за формулами (15) потребує m
ділень,
а
відшукання
за формулами
(16)

множень. Разом, обчислення правих частин перетвореної системи (8) потребує
дій множення і ділення.
Усього для реалізації прямого ходу методу Гаусса необхідно виконати
дій.
4.Для реалізації зворотнього ходу методу Гаусса за формулами (10) необхідно

множень.
Всього, для реалізації методу Гаусса необхідно виконати

дій
множення і
ділення, причому
основний час
витрачається
на прямий хід.
Для великих
m
число
дій множення
і ділення у
методі Гаусса
близьке до
За витратами
часу та необхідній
машинній пам’яті
метод Гаусса
придатний для
розв’язання
систем рівнянь
(2) загального
вигляду з кількістю
змінних
m порядку
100.
ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ .
Пусть
имеется функция
которую необходимо
продифференцировать
несколько раз
и найти эту
производную
в некоторой
точке.
Если задан явный вид функции, то выражение для производной часто оказывается достаточно сложным и желательно его заменить более простым. Если же функция задана только в некоторых точках (таблично), то получить явный вид ее производных ввобще невозможно. В этих ситуациях возникает необходимость приближенного (численного) дифференцирования.
Простейшая идея численного дифференцирования состоит в том, что функция заменяется интерполяционным многочленом (Лагранжа, Ньютона) и производная функции приближенного заменяется соответствующей производной интерполяционного многочлена

Рассмотрим простейшие формулы численного дифференцирования, которые получаются указанным способом.
Будем предполагать, что функция задана в равностоящих узлах
![]()
Ее
значения и
значения производных
в узлах будем
обозначать
![]()
Пусть
функция задана
в двух точках
и
ее значения
Посстроим интерполяционный многочлен первой степени
![]()
Производная
равна

![]()
Производную
функцию
в точке
приближенно
заменяем производной
интерполяционного
многочлена
(1)
Величина
называется
первой
разностной
производной.
Пусть
задана в трех
точках
Интерполяционный многочлен Ньютона второй степени имеет вид
![]()
Берем производную
![]()
В точке
она равна

Получаем приближенную формулу
(2)
Величина
называется
центральной
разностной
производной.
Наконец, если взять вторую производную
получаем
приближенную
формулу.
(3)
Величина
называется
второй
разностной
производной.
Формулы (1)-(3) называются формулами численного дифференцирования.
Предполагая
функцию
достаточное
число раз непрерывно
дифференцируемой,
получим погрешности
приближенных
формул (1)-(3).
В дальнейшем нам понадобится следующая лемма.
Лемма 1.
Пусть
произвольные
точки,
Тогда существует
такая точка
что

Доказательство. Очевидно неравенство
По теореме
Больцано-Коши
о промежуточных
значениях
непрерывной
функции на
замкнутом
отрезке она
принимает все
значения между
и
Значит существует
такая точка
что выполняет
указанное в
лемме равенство.
Погрешности формул численного дифференцирования дает следующая лемма.
Лемма 2.
1.Предположим,
что
Тогда существует
такая точка
, что
(4)
Если
то существует
такая точка
, что
(5)
Когда
то существует
такая, что
(6) Доказательство.
По формуле
Тейлора

откуда следует (4).
Если
то по формуле
Тейлора
(7)
где
![]()
Подставим
(7) в
Получаем

Заменяя в соответствии с леммою 1
![]()
получаем

Откуда и следует (6).
Равенство (5) доказывается аналогично ( доказательство провести самостоятельно).
Формулы (4)-(6) называются формулами численного дифференцирования с остаточными членами.
Погрешности формул (1)-(3) оцениваются с помощью следующих неравенств, которые вытекают из соотношений (4)-(6):

Говорят,
что погрешность
формулы (1) имеет
первый
порядок относительно
(или порядка
), а погрешность
формул (2) и (3) имеет
второй
порядок относительно
(или порядка
). Также говорят,
что формула
численного
дифференцирования
(1) первого
порядка точности
(относительно
),
а формулы (2) и
(3) имеют второй
порядок точности.
Указанным способом можно получать формулы численного дифференцирования для более старших производных и для большего количества узлов интерполирования.
Выбор
оптимального
шага. Допустим,
что граница
абсолютной
погрешности
при вычислении
функции
в каждой точке
удовлетворяет
неравенству
(8)
Пусть в
некоторой
окрестности
точки
производные,
через которые
выражаются
остаточные
члены в формулах
(5), (6), непрерывны
и удовлетворяют
неравенствам
(9)
где
- некоторые
числа. Тогда
полная погрешность
формул (2), (3) (без
учета погрешностей
округления)
в соответствии
с (5), (6), (8), (9)не превосходит
соответственно
величин
Минимизация
по
этих величин
приводит к
следующим
значениям