1.2.5 Другие задачи, решаемые численными методами
Область применения численных методов в математике огромна. Они применяются и при решении различных уравнений, и при вычислении определенных интегралов, и в приближении функции.
Рассмотрим различные способы решения уравнений.
Метод половинного деления (дихотомия)
Пусть мы нашли такие точки a и b что f(a)f(b)0, т. е. на отрезке [a,b] лежит не менее одного корня уравнения. Найдем середину отрезка xc=(a+b)/2 и вычислим f(xc). Из двух половин отрезка выберем ту, для которой f(xc)f(a или b)0, т.е. отрезок на котором функция меняет знак. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 9).
Размещено на http://www.allbest.ru/
Если требуется найти корень с точностью , то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f(x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций (т.к. длина отрезка, на котором лежит корень, после 10 итераций равна 1/210=1/102410-3). Зато точность ответа гарантируется.
Перечислим недостатки метода.
1. Для начала расчета надо найти отрезок, на котором функция меняет знак.
2. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс (хотя к одному из них сойдется).
3. Метод неприменим к корням четной кратности.
4. Для корней высокой нечетной кратности он сходится, но менее точен и хуже устойчив к ошибкам округления, возникающим при вычислении f(x).
5. На системы уравнений дихотомия не обобщается.
Утверждение 1. С помощью данного метода невозможно найти корни чётной кратности.
Доказательство.
Чётно кратный корень это корень уравнения вида
(x+a)2n=0,
где n - целое, n[0,].
Решением этого уравнения будет корень 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,
где n1,…,n(k+m) [0,] - целые числа; x1 x2… xk+m.
В уравнении k чётно кратных и m нечётно кратных корней. Оно раскладывается на (k+m) уравнений, из которых легко получаются корни. Если задать начальный отрезок [-x1-r,-x1+r], где r - мало, и проверить условие смены знака функции на его границах, то обнаружим, что знак не меняется в силу чётности степени. А если аналогично проверить нечётно кратные корни, то получим обратную ситуацию.
Следствие 1.
Если корень имеет чётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет одинаковые знаки.
Следствие 2.
Если корень имеет нечётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет разные знаки.
Пусть на заданном отрезке [a,b] лежит 1 корень чётной кратности, тогда в силу следствия 1 на границах отрезка знак меняться не будет, что означает остановку выполнения итераций и недостижение необходимой точности. Если же на отрезке [a,b] лежит 1 чётно кратный корень и 1 нечётно кратный корень, то чётно кратный корень будет просто игнорирован методом, т.к. условие смены знака являющееся также основным условием, с помощью которого определяется корень на текущем полуотрезке, в силу следствия 1 не выполнится. Следовательно, чётно кратный корень не может быть найден с помощью данного метода.
Утверждение 2. Если на концах начального отрезка значения функции имеют один знак, то метод может не сойтись, то есть, возможно, ни один из корней не будет найден с заданной точностью.
Утверждение 3. Если на концах начального отрезка значения функции имеют разные знаки, то будет найден с заданной точностью один из корней лежащих на нём.
Метод секущих
В данном методе, в отличие от метода Ньютона, проводятся не касательные, а секущие (Рис. 10). Из рисунка легко получить итерационную формулу:
.
Размещено на http://www.allbest.ru/
В качестве начального приближения необходимо задать не только x0, но и x1. Метод секущих имеет одно преимущество перед методом Ньютона - здесь не нужно вычислять производную. Но этот метод имеет также существенные недостатки. Сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня [7, C.39].
В знаменателе формулы стоит разность значений функции. Вдали от корня это не существенно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение не велико, а для кратных может быть существенным.
От «разболтки» страхуются так называемым приёмом Гаврика. Выбирают не очень малое е, ведут итерации до выполнения условия |xn+1-xn|<е и затем продолжают расчёты до тех пор, пока |xn+1-xn| убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют. Все ограничения по сходимости итераций для данного метода такие же, как и в методах простых итераций и Ньютона. А вот определение достижения заданной точности, как видно из описания метода, затруднительно, и, даже, возможна ситуация, когда из-за «разболтки» счёта заданная точность не будет достигнута никогда. При использовании метода секущих в явном виде определить точность трудно, поэтому используют косвенный метод. Считают, что вблизи корня |xn+1-xn||xт-xn+1|. Конечно эта оценка весьма примерна, но при больших n (в идеале при n>?) это так и есть.
- Введение
- 1. Общая теоретическая часть
- 1.1 Действия с приближенными величинами
- 1.2 Основные численные методы
- 1.2.1 Решение алгебраических и трансцендентных уравнений
- 1.2.2 Интерполяция функций
- 1.2.3 Метод наименьших квадратов и его применение
- 1.2.4 Численное интегрирование
- 1.2.5 Другие задачи, решаемые численными методами
- 2. Применение метода наименьших квадратов к построению эмпирических функциональных зависимостей
- 3. Расчетная часть
- Заключение
- 1.1. Математическое моделирование и численные методы
- «Разработка программного комплекса решения математической задачи численными методами»
- 6.1 Математические модели и численные методы решения задач в различных предметных областях
- Численные методы построения математических моделей
- 7.3. Численные методы решения уравнений,
- §8. Математические модели и численные методы.