Численные методы

Содержание

Решение алгебраических, нелинейных и трансцендентных уравнений

Метод половинного деления (дихотомия)

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

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

Метод секущих

Численные методы вычисления определённых интегралов

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

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

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

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

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

а

Приближение функций

Интерполяция

Аппроксимация

Список использованной литературы

Решение алгебраических, нелинейных и трансцендентных уравнений

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

f(x)=0. (1)

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

Первая и вторая задачи решаются аналитическими и графическими методами.

Когда ищутся только действительные корни уравнения, то полезно составить таблицу значений f(x). Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один. Но выявить по таблице корни чётной кратности* сложно. По таблице можно построить график функции у=f(х) и графически найти точки его пересечения с осью абсцисс. Этот способ более нагляден и дает неплохие приближенные значения корней. Во многих задачах техники такая точность уже достаточна. В технике еще популярны графические методы решения уравнений (номография). Построение графика позволяет выявить даже корни чётной кратности.

Иногда удается заменить уравнение (1) эквивалентным ему уравнением j(х)=y(х), в котором функции y1=j(х) и y2=y(х) имеют несложные графики. Например, уравнение хsinх—1=0 удобно преобразовать к виду sinx=l/x. Абсциссы точек пересечения этих графиков будут корнями исходного уравнения.

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

Метод половинного деления (дихотомия)

Пусть мы нашли такие точки a и b что f(a)f(b)£0, т. е. на отрезке [a,b] лежит не менее одного корня уравнения. Найдем середину отрезка xc=(a+b)/2 и вычислим f(xc). Из двух половин отрезка выберем ту, для которой f(xc)f(a или b)£0, т.е. отрезок на котором функция меняет знак. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 1).

Если требуется найти корень с точностью e, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2e. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f(x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций (т.к. длина отрезка, на котором лежит корень, после 10 итераций равна 1/210=1/1024»10-3). Зато точность ответа гарантируется.

Перечислим недостатки метода.

1. Для начала расчета надо найти отрезок, на котором функция меняет знак.

2. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс (хотя к одному из них сойдется).

3. Метод неприменим к корням четной кратности.

4. Для корней высокой нечетной кратности он сходится, но менее точен и хуже устойчив к ошибкам округления, возникающим при вычислении f(x).

5. Наконец, на системы уравнений дихотомия не обобщается.

Утверждение 1. С помощью данного метода невозможно найти корни чётной кратности.

Доказательство.

Чётно кратный корень это корень уравнения вида

(x+a)2n=0, где n – целое, nÎ[0,¥]. (2)

Решением этого уравнения будет корень x=-a кратности 2n. В общем виде уравнение может иметь как чётно, так и нечётно кратные корни. Можно записать общий вид уравнения имеющего (k+m) только действительных корней так:

(x+x1)2n1(x+x2)2n2…(x+xk)2nk(x+xk+1)2n(k+1)+1(x+xk+2)2n(k+2)+1…(x+xk+m)2n(k+m)+1=0, (3)

где n1,…,n(k+m) Î[0,¥] – целые числа; x1¹ x2¹…¹ xk+m.

В уравнении (3) k чётно кратных и m нечётно кратных корней. Оно раскладывается на (k+m) уравнений, из которых легко получаются корни. Если задать начальный отрезок [-x1-r,-x1+r], где r – мало, и проверить условие смены знака функции на его границах, то обнаружим, что знак не меняется в силу чётности степени. А если аналогично проверить нечётно кратные корни, то получим обратную ситуацию.

Следствие 1.

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

Следствие 2.

Если корень имеет нечётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет разные знаки.

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

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

Доказательство.

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

Если f(a)f(b)³0, то продолжать итерации невозможно, т.к. условие смены знака не подтверждается. Если же, тем не менее, на первом шаге не проверять условие смены знака и разделить отрезок пополам, то может возникнуть ситуация, в которой корни распределяться по чётному количеству в каждой половине отрезка. А чётное количество корней означает чётное количество пересечений оси Ox, даже если существуют кратные корни.

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

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

Доказательство.

 Скачать реферат