Ключевые слова: программирование, язык программирования, уравнение, решение, корень, метод деления отрезка пополам, отрезок, пример, скачать, c++, pascal, visual basic for applications, vba, doc, php, форма, лекции по программированию

Автор: Приходько Максим Александрович

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

Метод деления отрезка пополам основывается на следующем утверждении: если непрерывная функция на концах некоторого отрезка принимает значения разного знака, то где-то "внутри" этого отрезка она обязательно должна равняться нулю.

Естественно, как и в случае Вычисления площади фигуры, ограниченной графиком функции, корень уравнения практически никогда не находится точно, а с некоторой точностью e. Это значит, что найденное значение x* отличается по модулю от точного значения корня x на величину меньше e: |x* - x| < e.

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

Дальнейшее решение задачи будем вести в предположении, что корень корректно локализован - задан отрезок [X1, X2], на котором функция F имеет ровно одну перемену знака (F(X1) * F(X2) < 0).

На каждом очередном шаге вычисляется середина отрезка X3, после чего определяется та из половин отрезка, на которой сохраняется перемена знака. И в зависимости от этого левый или правый конец исходного отрезка "переносится" в его середину:

  X3 = (X1 + X2) / 2

  If (F(X1) * F(X3) < 0) Then
   X2 = X3
  End If
  
  If (F(X3) * F(X2) < 0) Then
   X1 = X3
  End If

В результате получается отрезок [X1, X2] вдвое меньшей длины, на котором сохраняется перемена знака функции.

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

  If (F(X3) = 0) Then
   X1 = X3
   X2 = X3
  End If

В этом случае оба конца отрезка "стягиваются" в его середину.

Описанные действия продолжаются до тех пор, пока длина отрезка не станет меньше 2 e. Тогда середина полученного отрезка будет отстоять от каждого из своих концов на расстояние не больше e, а от корня - на расстояние меньше e (так как корень не попадает ни в один из концов отрезка, иначе выполнялось бы равенство F(X1) * F(X2) = 0, что противоречит описанному алгоритму, получающему на каждом шаге отрезок с переменой знака, то есть F(X1) * F(X2) < 0):

 Do While (Abs(X2 - X1) > 2 * E)
  X3 = (X1 + X2) / 2
  
  If (F(X3) = 0) Then
   X1 = X3
   X2 = X3
  End If
  
  If (F(X1) * F(X3) < 0) Then
   X2 = X3
  End If
  
  If (F(X3) * F(X2) < 0) Then
   X1 = X3
  End If
 Loop

Обратите внимание на запись условия, определяющего длину отрезка [X1, X2]. Если абстрагироваться от нашей задачи, то на очередном шаге возможно возникновение значений X2 меньших, чем X1. Тогда их разность X2 - X1 будет меньше 0, а 0 в свою очередь меньше любого положительного числа, в том числе 2 e. Таким образом, работа алгоритма может быть прервана досрочно, а решение уравнения найдено неправильно. Именно по этой причине для определения "близости" двух значений в смысле "расстояния между ними" используют не просто разность, а разность взятую по модулю. Вдвойне это верно в том случае, когда мы не можем заранее знать, как одно значение соотносится с другим (какое больше, а какое меньше).

Осталось заметить, что для "универсализации" метода вычисление корня уравнения F(x) = 0 целесообразно вычисление значения функции F в точке x выделить в отдельную функцию (в качестве примера рассматривается функция sin(x), а решаемое уравнение имеет вид sin(x) = 0):

Function F(X As Double) As Double
 Dim Y As Double
 
 Y = Sin(X)
 
 F = Y
End Function

Тогда полный код будет иметь следующий вид:

Function F(X As Double) As Double
 Dim Y As Double
 
 Y = Sin(X)
 
 F = Y
End Function
Sub equation_solve()
 Dim X1 As Double
 Dim X2 As Double
 Dim X3 As Double
 Dim E As Double
 
 X1 = Val(InputBox("Введите X1"))
 X2 = Val(InputBox("Введите X2"))
 E = Val(InputBox("Введите точность e"))
 
 Do While (Abs(X2 - X1) > 2 * E)
  X3 = (X1 + X2) / 2
  
  If (F(X3) = 0) Then
   X1 = X3
   X2 = X3
  End If
  
  If (F(X1) * F(X3) < 0) Then
   X2 = X3
  End If
  
  If (F(X3) * F(X2) < 0) Then
   X1 = X3
  End If
 Loop
 
 MsgBox ("x = " + Str((X1 + X2) / 2))
End Sub

Вот как этот код выглядит в редакторе VBA MS Word:

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

C++ (С++ Builder 4.0)

#include 
#pragma hdrstop

#include "stdio.h"
#include "math.h"

#pragma argsused
double F(double x)
{
  double y;

 y = sin(x);

 return y;
}

int main(int argc, char* argv[])
{
  float x1;
 float x2;
 float x3;
 float e;

 printf("x1 = ");
 scanf("%f", &x1);
 printf("x2 = ");
 scanf("%f", &x2);
 printf("e = ");
 scanf("%f", &e);

 while(fabs(x2 - x1) > 2 * e)
 {
  x3 = (x1 + x2) / 2;

  if(F(x3) == 0)
  {
   x1 = x3;
   x2 = x3;
  }

  if(F(x1) * F(x3) < 0)
  x2 = x3;

  if(F(x3) * F(x2) < 0)
  x1 = x3;
 }

 printf(("x = " + FloatToStr((x1 + x2) / 2)).c_str());
 scanf("%f", &e);
}
//---------------------------------------------------------------------------

Pascal (Turbo Pascal 7.0)

В разработке

PHP

В разработке

Работающая форма находится по адресу: http://www.argusm.com/unipo_eqsolve_divide.php

Вид формы для ввода данных:

Вид формы после нажатия кнопки "Вычислить" и результат работы:

Уважаемые читатели

Вы можете свободно использовать приведенные программы (исходные файлы можно скачать ниже). Убедительная просьба: при перепечатке кодов или фрагментов статьи, пожалуйста, указывайте ссылку на оригинал статьи: http://www.argusm.com/article.php?id=112 В случае возникновения вопросов или комментариев к описанной задаче свяжитесь с автором, воспользовавшись одним из Контактов.