ЧИСЛЕННЫЕ МЕТОДЫ

ЧИСЛЕННЫЕ МЕТОДЫ

 

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

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

Этапы построения задач на ЭВМ:

1) Постановка задачи. На этом этапе формулируются условие задачи, математические термины или предпосылки. Далее определяется, что нужно найти и в каком виде представляется результат.

2) Построение математической модели. Модель – упрощенное по сравнению с реальностью описание объекта, явления, процесса. При этом учитываются только существенные с точки зрения исследователя свойства этого процесса. Модели бывают: математические, химические, физические и т.д.. Математическая модель – модель, которая сформулирована математически.

Требования к математической модели:

– требование простоты;

– адекватности;

3) Выбор полученной системы уравнений.

4) Разработка алгоритма решения полученной задачи (определение последовательности действий для достижения указанной цели).

5) написание алгоритма на языке какого-либо высокого уровня и отладка программы.

Тестирование задачи – решение задачи, которое уже известно, с некоторым набором исходных данных.

6) Получение решения задачи.

7) Анализ полученного решения.

 

МЕТОДИКА ОЦЕНКИ ПОГРЕШНОСТИ

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

Приближение числа. Погрешности.

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

Например.

Найдем по графику функции ее приближенное значение при x=1, 5:

если x=1, 5, то y 2, 3.

По формуле можно найти точное значение этой функции:

если x=1, 5, то .

Найдем абсолютную погрешность:

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

Например.

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

%.

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

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

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

Запись приближенных чисел.

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

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

Например.

Проверим цифру 7. Единица ее разряда 10> 0, 05. Значит она верная. Цифра 3: 1> 0, 05 – тоже верная. Аналогично верными будут и цифры 6 и 4: 0, 1> 0, 05, 0, 01> 0, 05, а вот цифра 2 будет сомнительной. Действительно, для 2: 0, 001< 0, 05.

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

Например.

Проверим цифру 7. Половина единицы ее разряда > 0, 05. Значит она верная. Цифра 3: > 0, 05 – тоже верная. Аналогично верной будет и цифры 6: 0, 05, а вот цифры 4 и 2 будут сомнительными. Действительно, для 4: 0, 005< 0, 05, 2: 0, 0005< 0, 05.

Оценка погрешности значений элементарных функций:

– абсолютная погрешность алгебраической суммы нескольких приближенных чисел равна сумме абсолютных погрешностей этих чисел;

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

Основные приемы приближенных вычислений:

– вычисления со строгим учетом погрешности (по правилам, описанным ранее);

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

Значащими называются все цифры, начиная с первой (слева), отличной от нуля.

Например.

– (3) значащие цифры;

– (3) значащие цифры;

– (4) значащие цифры.

Понятия устойчивости, корректности, сходимости

Устойчивость – чувствительность задачи к исходным данным. Задача называется устойчивой по исходному параметру x, если решение непрерывно от него зависит.

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

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

 

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Будем рассматривать уравнения вида f(x)=0 с изолированными корнями. – корень уравнения, если после подстановки, мы получаем f( )=0. Корень называется изолированным на отрезке [a; b], если внутри этого отрезка других корней не существует.

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

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

Решение уравнения складывается из двух этапов:

1) отделение (изолирование) корней;

2) уточнение значения корней.

Изолировать корни можно:

– аналитически. Для этого табулируем функцию на некотором отрезке. Табулирование функции – это вычисление значений функции при изменении аргумента от некоторого начального значения до некоторого конечного значения с определённым шагом. Именно так составляются таблицы значений функций, отсюда и название – табулирование.

xi	f(xi)
a=x0	f(x0)
x1	f(x1)
…	…
xi	f(xi)
xi+1	f(xi+1)
…	…
xn=b	f(xn)

– графически. Для этого уравнение f(x)=0 заменяют равносильным уравнением и строят графики функций y₁= и y₂= Абсциссы точек пересечения этих графиков дают приближенные значения искомых корней.

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

Итерационные методы.

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

Различают следующие методы решения:

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

 

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

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Рассмотрим произвольную систему m – линейных уравнений с n – неизвестными:

где – неизвестные переменные, – коэффициенты при неизвестных, – свободные члены системы.

Все методы решения систем линейных уравнений можно условно разбить на точные (прямые) и приближенные. К точным алгоритмам относят методы Крамера, Гаусса и т.д. Среди приближенных следует отметить прежде всего итерационные методы.

Гауссовы преобразования.

Рассмотрим два любых уравнения системы, выписав коэффициенты при неизвестных x_p и x_j в строках q и i:

x_p … x_j

q … a_qp … a_qj

i … a_ip ... a_ij

Преобразуем уравнение q так, чтобы коэффициент при x_p был равен 1, тогда коэффициенты при остальных переменных в этой строке будут равны: a'_qp (, путем перестановки уравнений всегда можно добиться этого условия). Исключим x_p из уравнения i, определив коэффициенты как a'_ij

Преобразование матриц по этим формулам называется гауссовым, a_qp – разрешающим элементом, строка q – разрешающей строкой, столбец p – разрешающим столбцом.

Из литературы широко известен метод Гаусса в различных модификациях:

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

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

Нахождение обратной матрицы.

Дана неособенная (невырожденная) матрица A =[ a_ij ]. Матрица называется невырожденной (неособенной), если ее определитель отличен от нуля. Требуется найти обратную матрицу A^-1. Матрица A^-1 =[ x_ij ] является обратной данной, если выполняется условие AA^-1 = E, где E – единичная матрица.

В результате перемножения матриц получим n систем n уравнений с n неизвестными: , где символ Кронекера. Чтобы найти A^-1 =[ x_ij ], необходимо решить эти системы уравнений. У всех этих систем одинаковые матрицы коэффициентов, разные только столбцы свободных членов. Это дает нам возможность решать все системы одновременно по схеме единственного деления.

Метод квадратных корней. Применяется для систем, имеющих симметрические матрицы коэффициентов. Квадратная матрица называется симметрической, если , то есть если равны элементы матрицы, симметричные относительно главной диагонали. Пусть дана линейная система уравнений АХ=В, где A =[ a_ij ] – симметрическая матрица. Тогда матрицу А можно представить в виде произведения двух транспонированных между собой треугольных матриц А = Т'Т, где Т' – нижняя треугольная матрица, Т – верхняя треугольная матрица. Матрица, в которой строки матрицы А являются столбцами называется транспонированной по отношению к матрице А. Отсюда найдем коэффициенты матрицы Т:

 

Подставим А = Т'Т в уравнение АХ=В, получим Т'Т Х=В. Обозначив Т Х через Y, Т' Y =В. получим Решение системы линейных уравнений АХ=В сводится к решению двух систем линейных уравнений: Т Х=Y и Т' Y =В. Из решения двух этих систем последовательно найдем:

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

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

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

Метод Зейделя.

Представляет собой некоторую модификацию метода итерации. Основная идея заключается в том, что при вычислении k-го порядка приближения неизвестной х_i неизвестные х_1, х₂, …., х_i-1. Обычно метод Зейделя дает лучшую сходимость, чем метод простой итерации.

ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ ПОЛИНОМАМИ

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

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

Постановка задачи интерполирования. Дана функция y=f(x) на отрезке [a; b]. Пусть в точках значения функции равны Требуется подобрать полином (многочлен) порядка не выше n таким образом, чтобы значения полинома в точках совпадали со значениями функции в этих точках, а при остальных значениях x из области определения должно выполняться приближенное равенство . Тогда функция называется интерполирующей, процесс ее построения – интерполированием, а точки узлами интерполирования.

Интерполирование – частный случай аппроксимации.

Интерполяционный полином Лагранжа. Пусть функция y=f(x) задана на отрезке [a; b]. Разобьем отрезок точками Требуется подобрать полином порядка не выше n таким образом, чтобы значения полинома в точках равнялись значениям функции в этих точках. Полином будем искать в виде линейной комбинации многочленов степени n:

где многочлены

нтерполяционный полином Лагранжа.

Например

для случая линейной интерполяции

для случая квадратичной интерполяции

Оценка погрешности.

, где при

Интерполяционные полиномы Ньютона. Применяются при равномерном разбиении.

Конечные разности. Пусть функция y=f(x) задана на отрезке [a; b]. Разобьем отрезок точками с постоянным шагом .

Данные разности называются конечными разностями I - порядка

…

 

Данные разности называются конечными разностями II - порядка

…

 

и т.д.

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

Например:

Порядок конечных разностей не превышает порядка исходного многочлена.

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

Первая Интерполяционная формула Ньютона (формула Ньютона для интерполирования вперед).

Постановка задачи. Пусть функция y=f(x) задана на отрезке [a; b]. Разобьем отрезок точками с постоянным шагом . Требуется подобрать полином порядка не выше n таким образом, чтобы значения полинома в точках равнялись значениям функции в этих точках.

,

…

Обозначим через , откуда

первая Интерполяционная формула Ньютона (формула Ньютона для интерполирования вперед).

Например

для случая линейной интерполяции

для случая квадратичной интерполяции

Оценка погрешности.

Вторая интерполяционная формула Ньютона (формула Ньютона для интерполирования назад).

Постановка задачи. Пусть функция y=f(x) задана на отрезке [a; b]. Разобьем отрезок точками с постоянным шагом .

Обозначим через , откуда

вторая интерполяционная формула Ньютона (формула Ньютона для интерполирования назад).

Оценка погрешности.

 

ОБРАТНОЕ ИНТЕРПОЛИРОВАНИЕ

Задача обратного интерполирования заключается в том, чтобы по заданному значению функции f(x) определить соответствующее значение аргумента. Если известно, что f(x) определена, монотонна и непрерывна в заданном промежутке, то в соответствующем промежутке значений функции f(x) существует однозначная обратная функция x=g(y), также монотонная и непрерывная по теореме об обратной функции. Если допустимаинтерполяция по переменной y, то обратную функцию x=g(y) можно заменить интерполяционным многочленом , удовлетворяющим условиям: При использовании интерполяционного полинома Лагранжа последний примет вид:

При равномерном разбиении отрезка применяют интерполяционный многочлен Ньютона:

отсюда , где

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

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

 

ПРИБЛИЖЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ

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

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

Аналогично можно найти и производные более высоких порядков.

ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ

Если функция f(x) непрерывна на отрезке [a; b] и известна первообразная F(x), то определенный интеграл от функции f(x) в заданных пределах может быть вычислен по формуле Ньютона-Лейбница:

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

Метод трапеции.

Пусть дана функция f(x) непрерывна на отрезке [a; b] и известна ее первообразная F(x). Требуется вычислить определенный интеграл функции f(x) в заданных пределах: .

Разобьем отрезок [a; b] точками с постоянным шагом . Тогда вместо интеграла рассмотрим сумму интегралов:

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

Аналогично находим и т.д.

Складывая полученные интегралы, получим:

Погрешность метода вычисляется по формуле:

.

Метод Симпсона.

Пусть дана функция f(x) непрерывна на отрезке [a; b] и известна ее первообразная F(x). Требуется вычислить определенный интеграл функции f(x) в заданных пределах: .

Разобьем отрезок [a; b] на четное количество отрезков точками с постоянным шагом . Тогда вместо интеграла рассмотрим сумму интегралов:

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

Аналогично находим и т.д.

Складывая полученные интегралы, получим:

Погрешность метода вычисляется по формуле:

.

 

 

ОБРАБОТКА ЭКСПЕРИМЕНТАЛЬНЫХ ДАННЫХ

Пусть некоторая функция получена в результате проведения эксперимента. Задача состоит в том, чтобы найти приближенную зависимость y=f(x), значения которой при x=x_i мало отличаются от опытных данных y_i. Полученная приближенная функциональная зависимость называется эмпирической формулой.

Этапы построения эмпирической формулы:

1) подбор общего вида формулы;

2) определение параметров формулы.

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

Метод наименьших квадратов.

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

Обозначим через . Чтобы определить параметры, необходимо найти частные производные от по каждому параметру и приравнять их к нулю: В итоге получим систему m +1 уравнений:

где при при

Решая системы уравнений, определим параметры эмпирической формулы.