воскресенье, 21 сентября 2008 г.

Основы информатики. Методы поиска корней уравнений. Метод хорд. Delphi.

Более быстродействующим, по сравнению с методом половинного деления, является способ поиска корня, названный МЕТОДОМ ХОРД. Графическая иллюстрация метода представлена на рисунке 1.6. Для построения алгоритма метода хорд необходима дополнительная информация о характере поведения функции на интервале поиска корня. Прежде всего, необходимо гарантировать, что на этом интервале функция монотонна (монотонно возрастает или монотонно убывает). Кроме того, на всем интервале не должен меняться характер выпуклости или вогнутости. Иными словами, на [a,b] не должны менять знак ни первая, ни вторая производные функции. Вообще говоря, даже и при нарушении этих условий метод хорд можно применять, но с использованием специальных приемов, на которых мы не будем останавливаться. Проще всего в сомнительных случаях просто сузить интервал до такого размера, на котором производные знак не меняют.

Рис. 1.6. Различные варианты в методе хорд

Из геометрии рисунка 1.6 (подобия треугольников) можно найти точку m пересечения хорды с осью абсцисс. Поскольку , то Дальнейшее построение алгоритма зависит от соотношения знаков первой и второй производных. Если знаки производных различны - левая часть рисунка 1.6, то новым правым концом интервала поиска корня становится точка m, то есть делается замена b на m. В противном случае, соответствующем двум вариантам правой части рисунка 1.6, делается замена на m. Итерационный процесс продолжается до достижения необходимой точности.
  Метод хорд действительно значительно более оперативен по отношению к методу деления отрезка пополам. В этом можно убедиться, реализовав оба метода для нахождения корня одного и того же уравнения на одном и том же отрезке и при одной и той же точности. Следует, однако, заметить, что выигрыш во времени будет иметь место только при оптимально написанной программе. В первую очередь, необходимо сократить до минимума количество вызовов функции f(x). Так в приведенном выше выражении для величины m по два раза фигурируют функции f(a) и f(b). Разумеется, функцию необходимо посчитать один раз, запомнить ее значение в какой-либо переменной и во второй раз использовать уже не вызов функции, а эту переменную.
  Рассмотренные методы не исчерпывают арсенала средств поиска корней уравнений. Существуют методы более оптимальные либо по времени, либо по расходованию памяти компьютера. Кроме того, имеются методики, оптимальные для конкретных видов функций, для которых решается уравнение. Так, например, существуют алгоритмы, позволяющие находить группы корней, если функция является алгебраическим полиномом (причем корни могут быть найдены в комплексной области). Алгоритмы эти выглядят, однако, довольно сложными и не могут быть рассмотрены здесь.

Решить уравнение sin(x)=0,5 на промежутке [0,1].

Программный код:
procedure TForm1.Button1Click(Sender: TObject);
var
 a,b,e,m,ms,s:real;
begin
  a:=0;
  b:=1;
  m:=1;
  e:=strtofloat(edit1.Text);
  s:=0;
  while abs((m-ms)/m)>e do
  begin
  ms:=m;
  m:=(a*(sin(b)-1/2)-b*(sin(a)-1/2))/((sin(b)-1/2)-(sin(a)-1/2));
  b:=m;
  s:=s+1;
  end;
  edit2.Text:=floattostr(m);
  edit3.Text:=floattostr(s*2);
end;

Скачать проект

4 комментария:

Unknown комментирует...

программа хороша, только вот одно интересно - что значит s? это количество повторений после while?
и ещё - зачем в выводе s умножаем на два? Также не пойму что такое ms.

Unknown комментирует...

странно..Ввёл программу в делфи, сделал форму под него, добавил чтобы он считывал a и b с edit полей. И выводит неправильный ответ. Я в MS Excel посчитал ответ, получился другой, на 0.2 примерно больше. Пожалуста, пересмотрите программу

[wiZArd] комментирует...

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

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

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

[wiZArd] комментирует...

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