Математическая модель. Решение нелинейных уравнений. Решение систем линейных алгебраических уравнений

1. Математическая модель.

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

2. Исходные данные.

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

3. Метод вычислений.

Применяемые для решения задачи методы как правило являются приближенными. Например, заменяют интеграл суммой, функцию - многочленом, производную - разностью и т. д. Погрешность метода необходимо определять для конкретного метода. Обычно ее можно оценить и проконтролировать. Следует выбирать погрешность метода так, чтобы она была не более, чем на порядок меньше неустранимой погрешности. Большая погрешность снижает точность решения, а меньшая требует значительного увеличения объема вычислений.

4. Округление в вычислениях.

Погрешность округления возникает из-за того, что вычисления производятся с конечным числом значащих цифр (для ЭВМ это 10 - 12 знаков). Округление производят по следующему правилу: если в старшем из отбрасываемых разрядов стоит цифра меньше пяти, то содержимое сохраняемых разрядов не изменяется; в противном случае в младший сохраняемый разряд добавляется единица с тем же знаком, что и у самого числа. При решении больших задач производятся миллиарды вычислений, но так как погрешности имеют разные знаки, то они частично взаимокомпенсируются.

Различают абсолютную и относительную погрешности. Пусть а - точное, вообще говоря неизвестное числовое значение некоторой величины, а а^* - известное приближенное значение этой величины, тогда величину

(а^*) = | а - а^*|

называют абсолютной погрешностью числа а^*, а величину

(а^*) =

- его относительной погрешностью.

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

Корректность

Решение задачи y* называется устойчивым по исходным данным x*, если оно зависит от исходных данных непрерывным образом. Это означает, что малому… Говорят, что задача поставлена корректно, если выполнены следующие три… 1. Решение существует при любых допустимых исходных данных.

Вычислительные методы

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

ЛЕКЦИЯ 9

  Обычно используется запись Определение. Пусть искомая величина u является функцией параметров u* — приближенное значение u. Тогда предельной…

ЛЕКЦИЯ 11

Тема: Решение нелинейных уравнений

Постановка задачи

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

f(x) = 0. (2.1)

Значение x^*, при котором f(x^*) = 0, называется корнем (или решением) уравнения (2.1).

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

Корень x^* уравнения (2.1) называется простым, если первая производная функции f(x) в точке x^* не равна нулю, т. е. f (x^*) 0. Если же f (x^*) = 0, то корень x^* называется кратным корнем.

Геометрически корень уравнения (2.1) есть точка пересечения графика функции y = f(x) с осью абсцисс. На рис. 2.1 изображен график функции y = f(x), имеющей четыре корня: два простых (xи x) и два кратных (xи x).

Рис. 2.1.

Большинство методов решения уравнения (2.1) ориентировано на отыскание простых корней уравнения (2.1).

Основные этапы отыскания решения

В процессе приближенного отыскания корней уравнения (2.1) обычно выделяют два этапа: локализация (или отделение) корня и уточнение корня.

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

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

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

На этапе уточнения корня вычисляют приближенное значение корня с заданной точностью > 0. Приближенное значение корня уточняют с помощью различных итерационных методов. Суть этих методов состоит в последовательном вычислении значений x₀, x₁, …, x_n, …, которые являются приближениями к корню x^*.

Метод деления отрезка пополам (метод дихотомии, метод бисекции)

Метод деления отрезка пополам является самым простым и надежным способом решения нелинейного уравнения.

Пусть функция f(x) непрерывна на отрезке [a0, b0] и принимает на концах отрезка значения разных знаков, т.е. f(a0)f(b0) < 0. (2.2) Разделим отрезок [a0, b0] пополам. Получим точку x0 = . Вычислим значение функции в этой точке: f(x0). Если f(x0) = 0,…

Рис. 2.2

Середина n-го отрезка x_n = . Очевидно, что длина отрезка [a_n, b_n] будет равна , а т. к. x^*[a_n, b_n], то

| x_n - x^*| . (2.3)

Погрешность метода. Оценка (2.3) характеризует погрешность метода деления отрезка пополам и указывает на скорость сходимости: метод сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/2. Заметим, что оценка (2.3) является априорной.

Критерий окончания. Из соотношения (2.3) следует, что при заданной точности приближения вычисления заканчиваются, когда будет выполнено неравенство b_n - a_n < 2 или неравенство n > log₂((b₀ - a₀)/) - 1. Таким образом, количество итераций можно определить заранее. За приближенное значение корня берется величина x_n.

Пример 2.1.

Найдем приближенно x = с точностью ??= 0.01. Эта задача эквивалентна решению уравнения x⁵ - 2 = 0, или нахождению нуля функции f(x) = x⁵ - 2. В качестве начального отрезка [a₀, b₀] возьмем отрезок [1, 2]. На концах этого отрезка функция принимает значения с разными знаками: f(1) < 0, f(2) > 0.

Найдем число n делений отрезка [1, 2], необходимых для достижения требуемой точности. Имеем:

| x_n - x^*| = 10^-2,

N6.

Следовательно, не позднее 6-го деления найдем с требуемой точностью, 1.1484. Результаты вычислений представлены в таблице 2.1.

Таблица 2.1

n	0 1 2 3 4 5 6
an	1.0000 1.0000 1.0000 1.1250 1.1250 1.1406 1.1406
bn	2.0000 1.5000 1.2500 1.2500 1.1875 1.1875 1.1562
xn	1.5000 1.2500 1.1250 1.1875 1.1406 1.1562 1.1484
Зн f(an)	- - - - - - -
Зн f(bn)	+ + + + + + +
f(xn)	5.5938 0.7585 -0.2959 0.1812 -0.0691 0.0532 -0.0078
bn - an	1.0000 0.5000 0.2500 0.1250 0.0625 0.0312 0.0156

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

Пусть уравнение (2.1) можно заменить эквивалентным ему уравнением

Например, уравнение - 0.5 = 0 можно заменить эквивалентным ему уравнением x = 0.5sinx. Выберем каким-либо образом начальное приближение x0. Вычислим значение функции… xn+1 = (xn). (2.5)

Метод Ньютона (метод касательных)

|xn - xn - 1| < . (2.18) Пример 2.3. Применим метод Ньютона для вычисления . где a > 0, p - натуральное число. Вычисление эквивалентно решению уравнения…

Метод секущих (метод хорд)

В этом и следующем разделе рассмотрим модификации метода Ньютона.

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

f (x_n) ,

то вместо формулы (2.13) получим

x_{n +1} = x_n -. . (2.20)

Это означает, что касательные заменены секущими. Метод секущих является двухшаговым методом, для вычисления приближения x_{n +1} необходимо вычислить два предыдущих приближения x_n и x_{n - 1} , и, в частности, на первой итерации надо знать два начальных значения x₀ и x₁.

Формула (2.20) является расчетной формулой метода секущих. На рис. 2.9 приведена геометрическая иллюстрация метода секущих.

Рис. 2.9

Очередное приближение x_{n +1} получается как точка пересечения с осью OX секущей, соединяющей точки графика функции f(x) с координатами (x_{n -1}, f(x_{n - 1})) и (x_n , f(x_n)).

Сходимость метода. Сходимость метода секущих устанавливает следующая теорема.

Теорема 2.4 Пусть x^* - простой корень уравнения f(x) = 0, и в некоторой окрестности этого корня функция f дважды непрерывно дифференцируема, причем f"(x) 0. Тогда найдется такая малая -окрестность корня x^*, что при произвольном выборе начальных приближений x₀ и x₁ из этой окрестности итерационная последовательность, определенная по формуле (2.20) сходится и справедлива оценка:

|x_{n + 1} - x^*| C |x_n - x^*| ^p, n 0, p = 1.618. (2.21)

Сравнение оценок (2.15) и (2.21) показывает, что p < 2, и метод секущих сходится медленнее, чем метод Ньютона. Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих - только функцию. Поэтому при одинаковом объеме вычислений в методе секущих можно сделать примерно вдвое больше итераций и получить более высокую точность.

Так же, как и метод Ньютона, при неудачном выборе начальных приближений (вдали от корня) метод секущих может расходиться. Кроме того применение метода секущих осложняется из-за того, что в знаменатель расчетной формулы метода (2.20) входит разность значений функции. Вблизи корня эта разность мала, и метод теряет устойчивость.

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

|x_n - x_{n - 1}| < . (2.22)

Пример 2.4.

Применим метод секущих для вычисления положительного корня уравнения 4(1 - x²) - e^x = 0 с точностью = 10^-3.

Корень этого уравнения находится на отрезке [0, 1], так как f (0) = 3 > 0, а f (1) = -e < 0. Подсчитаем вторую производную функции: f "(x) = -8 - e^x. Условие f(x)f " (x) 0 выполняется для точки b = 1. В качестве начального приближения возьмем x₀ = b = 1. В качестве второго начального значения возьмем x₁ = 0.5. Проведем вычисления по расчетной формуле (2.20). Результаты приведены в табл. 2.4.

Таблица 2.4

n	xn
	1.0000 0.5000 0.6660 0.7093 0.7033 0.7034

Метод ложного положения

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

ЛЕКЦИЯ 12

Тема: Решение систем линейных алгебраических уравнений

Постановка задачи

a11x1 + a12 x2 + a13x3 + … + a1nxn = b1 a21x1 + a22 x2 + a23x3 + … + a2nxn = b2 a31x1 + a32 x2 + a33x3 + … + a3nxn = b3 (3.1)

Метод исключения Гаусса. Схема единственного деления

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

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

Прямой ход состоит из n - 1 шагов. На первом шаге исключается переменная x₁ из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n-го уравнений вычесть первое, умноженное на величину

m = , i = 2, 3, …, n. (3.4)

При этом коэффициенты при x₁ обратятся в нуль во всех уравнениях, кроме первого.

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

a = a_ij - ma_1j , b= b_i - mb₁ (3.5)

Легко убедиться, что для всех уравнений, начиная со второго, a= 0, i = 2, 3, …, n. Преобразованная система запишется в виде:

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

ax₂ + ax₃ + … + ax_n = b

a x₂ + ax₃ + … + ax_n = b (3.6)

ax₂ + ax₃ + … + ax_n = b

Все уравнения (3.6), кроме первого, образуют систему (n - 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x₂. Точно так же исключаем переменную x₃ из последних n - 3 уравнений.

На некотором k-ом шаге в предположении, что главный элемент k-ого шага a0, переменная x_k исключается с помощью формул:

m = ,

a = a - ma ,

b= b - mb, i, j = k + 1, k + 2, …, n. (3.7)

Индекс k принимает значения 1, 2, …, n - 1.

При k = n - 1 получим треугольную систему:

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

ax₂ + ax₃ + …+ ax_n = b

ax₃ + …+ ax_n = b (3.8)

ax_n = b

с треугольной матрицей A_n.

Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса.

При использовании метода Гаусса нет необходимости в предварительном обосновании существования и единственности решения (т. е. доказательства, что det A 0). Если на k-ом шаге все элементы a (i = k, k + 1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения.

Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определяем x_n... Подставляя его в предпоследнее уравнение, находим x_n-1, и т. д. Общие формулы имеют вид:

x_n = ,

x_k = (b- a x_k+1 - a x_k+2 - … - a x_n), k = n - 1, n - 2, …, 1 (3.9)

Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 2/3n³ операций для прямого хода и n² операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3n³ + n².

Пример 3.1.

Применим метод исключения Гаусса по схеме единственного деления для решения системы уравнений:

2.0x₁ + 1.0x₂ - 0.1x₃ + 1.0x₄ = 2.7

0.4x₁ + 0.5x₂ + 4.0x₃ - 8.5x₄ = 21.9

0.3x₁ - 1.0x₂ + 1.0x₃ + 5.2x₄ = - 3.9 (3.10)

1.0x₁ + 0.2x₂ + 2.5x₃ - 1.0x₄ = 9.9

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

Прямой ход. 1-ый шаг. Вычислим множители:

m = = = 0.2; m = = = 0.15; m = = = 0.5.

Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m, m, m, получим новую систему:

2.0x₁ + 1.0x₂ - 0.1x₃ + 1.0x₄ = 2.7

0.3x₂ + 4.02x₃ - 8.70x₄ = 21.36

-1.15x₂ + 1.015x₃ + 5.05x₄ = - 4.305 (3. 11)

- 0.30x₂ + 2.55x₃ - 1.50x₄ = 8.55

2-ой шаг. Вычислим множители:

m = = = - 3.83333; m = = = -1.0.

Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m и m, приходим к системе:

2.0x₁ + 1.0x₂ - 0.1x₃ + 1.0x₄ = 2.7

0.3x₂ + 4.02x₃ - 8.70x₄ = 21.36

16. 425x₃ - 28.300x₄ = 77.575 (3.12)

6.570x₃ - 10.200x₄ = 29.910

3-ий шаг. Вычислим множитель:

m = = = 0.4.

Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m, приведем систему к треугольному виду:

2.0x₁ + 1.0x₂ - 0.1x₃ + 1.0x₄ = 2.7

0.3x₂ + 4.02x₃ - 8.70x₄ = 21.36

16. 425x₃ - 28.300x₄ = 77.575 (3.13)

1.12x₄ = -1.12

Обратный ход. Из последнего уравнения системы (3.13) находим x₄ = 1.000. Подставляя значение x₄ в третье уравнение, получим x₃ = 2.000. Подставляя найденные значения x₄ и x₃ во второе уравнение, найдем x₂ = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x₄, x₃ и x₂, вычислим x₁ = -1.000.

Итак система (3.10) имеет следующее решение:

x₁ = 1.000, x₂ = 2.000, x₃ = 3.000, x₄ = - 1.000.

Метод исключения Гаусса с выбором главного элемента по столбцу

Трудоемкость метода. Дополнительные действия по выбору главных элементов требуют примерно n2 операций, что практически не влияет на общую… Пример 3.2. Применим метод исключения Гаусса с выбором главного элемента по столбцу для решения системы уравнений (3.10) из…

Вычисление определителя методом исключения Гаусса

det A = (-1)s det An, где s - число перестановок строк, (s = 0, если использовался метод Гаусса по… det A = (-1)s a11 aa …a (3.17)

Вычисление обратной матрицы методом исключения Гаусса

A A-1 = E, (3.18) где E - единичная матрица: 1 0 0 … 0

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

Для того, чтобы применить метод простой итерации, необходимо систему уравнений Ax = b (3.22) с квадратной невырожденной матрицей A привести к виду

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

В методе Якоби на (k+1)-ой итерации значения x, i = 1, 2, …, n. вычисляются подстановкой в правую часть (3.27) вычисленных на предыдущей итерации… x = b12 x + b13 x + … + b1,n-1 x + b1n x + c1 x = b21 x + b23 x + … + b2,n-1 x + b2n x + c2

ЛЕКЦИЯ 13

Тема: Приближение функций

Постановка задачи

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

Приближение функции многочленами Тейлора

f(x) = c0 + c1(x - a) + c2(x - a)2 + … + cn(x - a )n + Rn(x) = Tn(x) + Rn(x), где ck =

Интерполяция функции многочленами Лагранжа

P(x) = a0 + a1x + a2x2 + … + amxm, (4.5) который бы в узлах xi, i = 0, 1, … , n принимал те же значения, что и исходная… P(xi) = yi, i = 0, 1, … , n. (4.6)

Аппроксимация функций. Метод наименьших квадратов

Рис.4.2 При аппроксимации желательно получить относительно простую функциональную… Эта функциональная зависимость должна с достаточной точностью соответствовать исходной табличной зависимости. В…

ЛЕКЦИЯ 14

Тема: Численное интегрирование функций одной переменной

Постановка задачи численного интегрирования

I == F(b) - F(a), (5.1) где F(x) - первообразная функции f(x). Например, в элементарных функциях не… Суть численного интегрирования заключается в том, что подынтегральную функцию f(x) заменяют другой приближенной…

Метод прямоугольников

Рис. 5.1 Разобьем отрезок [a, b] на n равных частей длиной h, так, что h = . При этом… Рис. 5.2

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

Рис. 5.7 Тогда площадь криволинейной трапеции приближенно можно считать равной площади… I=Iтр =h= (5.7)

Метод Симпсона (метод парабол)

y = L2(x) = f(x) + (x - x) + (x - x)2, (5.9) где h = .

Правило Рунге практической оценки погрешности

I - Ih Chk, (5.15) где Ih приближенное значение интеграла, вычисленное по одной из формул (5.3),… Если уменьшить шаг h в два раза, то, в соответствии с (5.15) получим:

Лекция 15

Тема: Численное решение дифференциальных уравнений

Постановка задачи Коши

y (t) = f(t, y(t)). (6.1) Решением уравнения (6.1) является дифференцируемая функция y(t), которая при… Рис. 6.1

Метод Эйлера

Будем решать задачу Коши y (t) = f(t, y(t)). y(t0 ) = y0,

Модифицированные методы Эйлера

y = yi + fi = yi +f(ti, yi). Затем находится значение правой части уравнения (6.1) в средней точке f = f(t, y)

Метод Рунге - Кутта

Рассмотрим задачу Коши для дифференциального уравнения y (t) = f(t, y(t)) с начальным условием y(t0 ) = y0.