Интернет-сообщество учителей информатики г. Слободского Четверг, 28.03.2024, 22:24
Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Форум » Разделы » Домашнее задание по информатике » Задача по решению нелинейного уравнения
Задача по решению нелинейного уравнения
TyroxineДата: Воскресенье, 14.10.2012, 02:17 | Сообщение # 1
Рядовой
Группа: Пользователи
Сообщений: 3
Награды: 0
Репутация: 0
Статус: Offline
Пусть имеется уравнение с одним неизвестным
F (x) = 0, (1)
где F (x) — заданная непрерывная функция. Произвольное нелинейное уравнение вида (1) может иметь одно или несколько (в том числе, бесконечно много) решений либо вовсе не иметь ни одного решения. Однако мы не ставим цель найти все решения (или хотя бы определить их число). Речь пойдет о более ограниченных задачах: найти решение на заданном отрезке a <= x <= b (предполагая, что факт его существования заранее известен), или найти некоторое решение, зная для него грубую оценку (начальное приближение).

Метод деления отрезка
Метод деления отрезка (называемый также методом бисекции или дихотомии) — очень простой, но вполне надежный численный метод нахождения корня уравнения (1) на заданном отрезке. К его достоин- ствам относится отсутствие каких-либо специальных требований к свой- ствам функции F (x) (кроме ее непрерывности); недостатком является сравнительно медленная сходимость.
Перед началом работы должен быть задан отрезок [a, b ], на концах которого значения функции отличны от нуля и имеют противоположные знаки:
F (a) • F (b) < 0, (6)
причем внутри отрезка должен находиться только один корень (функция должна проходить через нуль единственный раз).
Один шаг алгоритма состоит из следующих действий:
• Найти середину отрезка (точку c);
• Вычислить значение функции в средней точке F ( c );
• Проверить условие F ( c ) = 0 (или более слабое условие (2)); если оно выполнено, то c является искомым решением (точное равенство F © = 0 маловероятно, но проверить его все же необходимо, так как для правильного выполнения остальных действий нужна гарантия, что значение функции отлично от нуля);
• Проверить, не достигнута ли требуемая точность определения корня (условие (5)). Если условие выполнено, принять точку c за ис- комое приближенное решение x и закончить работу, иначе продолжать поиск корня;
• Сравнить знак F ( c ) со знаком функции на одном из концов отрезка
(например, левом). Если знаки противоположны,
F (a) • F ( c ) < 0, (7)
то корень находится на левой половине отрезка, в противном случае — на правой. Заменить исходный отрезок соответствующей половиной (т. е. подставить c на место одной из граничных точек a, b так, чтобы сохранялось условие (6)) и перейти к началу нового шага.
Как следует из изложенного выше алгоритма, он применим лишь для поиска простых корней, когда график функции F (x) пересекает ось x. В случае кратных корней (F (x) обращается в нуль в точке касания оси x, как, например, для уравнения x2 = 0) метод деления отрезка не работает.
При программировании метода деления отрезка следует прежде всего проверить выполнение исходных предпосылок, т. е. отличие функции от нуля на границах заданного отрезка и условие (6). Это условие может быть нарушено вследствие вычислительных погрешностей, если искомое решение находится в непосредственной близости от левой или правой граничной точки. В этом случае приближенным решением должна стать точка a или b (но предварительно нужно убедиться, что значение функ- ции в ней достаточно мало в смысле условия (2); если это не так, то мы, скорее всего, просто имеем дело с ошибкой при задании отрезка).

Добавлено (14.10.2012, 02:17)
---------------------------------------------
Есть еще две вычислительные тонкости, которые желательно учесть. Первая из них связана с определением точки c. Очевидная формула
c = (a+b)/2
хотя и является совершенно справедливой с математической точки зре- ния, может приводить к неожиданным эффектам из-за особенностей ма- шинной арифметики. Рассмотрим пример, предполагая для простоты, что мы имеем дело с числами, содержащими 3 цифры в мантиссе. Пусть a = 0.632, b = 0.634 (т. е. левая и правая границы отрезка сблизились, и процесс уже близок к завершению). Пытаемся вычислить среднюю точку: c = (0.632 + 0.634)/2 = 1.27/2 = 0.635 (!) Полученный результат неожиданно оказался вообще за пределами отрезка. Легко видеть, что
причиной ошибки явилось округление суммы (1.266) до трех значащих цифр (1.27) перед делением пополам. Подобной неприятности можно избежать, переписав формулу так, чтобы середина получалась как ре- зультат добавления небольшой поправки к левой границе отрезка:
с = a + (b-a)/2
Так, для приведенного выше примера c = 0.632 + [(0.634 − 0.632)/2] =
0.632 + 0.001 = 0.633.
Вторая тонкость касается проверки условий типа (6) и (7). Дело в том, что в машинной арифметике существует граница малости ненуле- вых чисел, и числа, меньшие этой границы, заменяются нулем. Напри- мер, для чисел типа real в языке Pascal граница машинного нуля имеет величину порядка 10−38. Предположим, что F (a) = 10−25, F © = −10−25. Попытка вычислить произведение этих значений должна была бы дать
−10−50, но вместо этого получится машинный нуль, и результат сравнения знаков окажется неправильным. Заметим, что такой исход вполне реален, поскольку мы приближаемся к точке, где F (x) обращается в нуль, и следовательно, малые значения функции весьма вероятны. Что- бы сравнение знаков всегда выполнялось правильно, можно использо- вать математическую функцию sign x, которая принимает значения +1 и −1 при положительных и отрицательных значениях аргумента, соот- ветственно. Вместо (7) следует проверять условие
sign F (a) • sign F © < 0,
что вполне безопасно при любых ненулевых значениях функций. Един- ственное неудобство состоит в том, что в языке C нет стандартной функ- ции sign, и ее придется написать самостоятельно. Возможный вариант — представить sign F (x) как F (x)/|F (x)|, хотя это и не самый эффективный путь в смысле вычислительных затрат.

Сообщение отредактировал Tyroxine - Воскресенье, 14.10.2012, 02:16
 
Форум » Разделы » Домашнее задание по информатике » Задача по решению нелинейного уравнения
  • Страница 1 из 1
  • 1
Поиск:

Интернет-сообщество учителей информатики г.Слободского © 2024Конструктор сайтов - uCoz