Программирование на ЭВМ

    Для работы метода не обязательно задавать отрезок, содержащий корень уравнения f(x)=0. Достаточно знать лишь начальное приближение корня x=C₀. Иллюстрация работы метода приведена на рис.1.3.

      
 
 
 
 
 
 
 
 
 
 
 
 

    Рис.1.3 – Метод касательных

    Проводим  касательную к кривой y = f (x) в т. М₀ и находим точку её пересечения с осью Х. Это и будет новое приближение х=С₁. В точке М₁ снова проводим касательную к f (x) и т.д.

    Уравнение касательной, проведенной к кривой y=f (x) в т. М₀(C₀, f(C₀)):

      y – f (C₀) = f ′ (C₀)(x-C₀), откуда

    y = f (C₀)+f′(C₀)(x-C₀).

      Полагаем y=0 и находим x=C₁:

     Аналогично  находим С₂ и т.д.

    Таким образом, рекуррентная последовательность для С будет иметь вид:

    

              
 
 
 

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

           

                  Метод хорд (линейной  интерполяции)

    Пусть нам известно, что корень находится  внутри отрезка [a, b] (рис.1.4). Вычисляем значения f(a), f(b) и проводим прямую, соединяющую точки A и B (хорду). Точка С₀,  в которой прямая AB пересекается с осью Х, есть начальное приближение к корню. Сравниваем знаки f(C₀) и f(b).

    

Если  они одинаковы, то переходим к  отрезку [a, C₀], иначе к [C₀, b]. Для нового отрезка проделываем то же самое, находя в результате точку С₁, и т.д. Таким образом, на каждом

отрезке приближенно заменяем кривую f(x) отрезком прямой, с чем и связано название метода. Отрезок постепенно сужается, однако не путем деления пополам (во многих случаях – быстрее). Чтобы построить рекуррентную последовательность для С_i, нужно знать уравнение прямой AB:

     .

    В точке пересечения прямой с осью абсцисс значение y=0, откуда получим x=C₀:

     .

    После нахождения границ нового отрезка вычисляем по той же формуле С₁ и т.д. Алгоритм, реализующий метод хорд, напоминает алгоритм для метода дихотомии, но значения С_i вычисляются по другой формуле.

    Алгоритм  нахождения корней методом хорд.

    Задать значение EPS;

    READ (A,B); Y:=F(A);

    IF Y*F(B)>0 THEN WRITELN (‘неверные данные’);

    ELSE BEGIN

                FA:=Y;

                FB=F(B);

                WHILE ABS(Y)>=EPS DO

                      BEGIN

                      X:=A-(B-A)*FA/(FB-FA);

                      Y:=F(X);

                      IF Y*FB<0 THEN BEGIN

                                        A:=X; FA:=Y;

                                        END

                      ELSE BEGIN 

                            B:=X; FB:=Y;

                                END;

                      END;

                WRITELN(X);

    END

 

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

    Для использования этого метода уравнение  f(x)=0 нужно представить в виде g(x)-x=0 или

    x=g(x).       (1)

    Пусть известно начальное приближение  корня x=C₀. Подставляем это значение в правую часть уравнения (1). Получим C₁=g(C₀). Новое значение C₁ снова подставляем в (1) и т.д. Алгоритм будет сходиться при условии, что . Рекуррентная последовательность:

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

    Оценка  трудоемкости алгоритмов

    Мы  рассмотрели несколько алгоритмов отыскания корней функции.

Для любого алгоритма нужно уметь оценивать количество вычислений, требуемых при его работе. Это является косвенной оценкой быстродействия алгоритма. Может оказаться, что алгоритм работает слишком медленно и непригоден для данной конкретной функции. Линейный (последовательный) алгоритм работает очень быстро. Иначе обстоит дело с  циклическими алгоритмами. Для них нужно уметь вычислять количество шагов алгоритма, то есть количество выполнений цикла.

    Оценим  трудоемкость (по числу шагов) метода дихотомии. Критерием окончания  вычислений является достижение интервалом d (то есть погрешностью вычисления корня) заданной величины. Пусть нужно уменьшить d в M раз. Возникает вопрос: сколько раз при этом должен  проработать цикл? Обозначим число выполнений цикла через N. Так как

d_i=d_i-1/2, то для M=1 N=0, для M=2 N=1, для M=4 N=2, для M=8 N=4, для M=16 N=4 и т.д. Следовательно,

    M = 2^N , откуда

    N= élog₂Mù – округляем до ближайшего целого в большую сторону.

Таким образом оказывается, что для M=1000 N=10, а для M=1 000 000

N=20.

    Можно сказать, что такой алгоритм достаточно хорош. Проработав 20 раз, он улучшит точность результата в 1 000 000 раз. Такие алгоритмы называются алгоритмами с логарифмической трудоемкостью. К ним относится метод дихотомии.

    1.6. Проверка правильности  алгоритмов

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

    Актуальность  вопроса можно проиллюстрировать  на таком примере: пусть вероятность  того, что алгоритм, занимающий 1 страницу текста, верен, равна 0.9 (из 10 операторов 1 неверный, для начинающих программистов правильнее было бы 9 из 10). Для алгоритма, занимающего 2 страницы – 0.9²=0.81, 3 страницы – 0.9³ и т.д. Для современных ЭВМ часто длина программы ≈ 100 страниц. Вероятность правильной работы при этом 0.9¹⁰⁰=0.000027 – ничтожно мала.

    Говорят, что ошибки в программах появились  раньше, чем сами машины. Можно выделить три источника ошибок.

        “Описки”, то есть ошибки, появившиеся из-за невнимательности и незначительных нарушений синтаксиса языка.

        Алгоритмические ошибки. Возникают  из-за неправильного понимания  сути алгоритма или неправильного  выражения мыслей. Это более серьезные  ошибки.

        Ошибки, возникающие при работе  с такими значениями данных, на  которые не рассчитана программа. То есть ошибки из-за неправильных данных. Например, 20! – слишком большое число, 1/(20!) – слишком маленькое. Такие ошибки нужно предвидеть.

    Методы  борьбы с различными группами ошибок различны.

        Большая часть “описок” обнаруживается  на этапе перевода (автоматического) нашего алгоритма в команды ЭВМ – на так называемом этапе трансляции.

    Другая  часть “описок”, а также некоторые  алгоритмические ошибки, может быть найдена путем тестирования. Исторически  первым методом проверки правильности алгоритма (программы) явилось тестирование: программа вводится в ЭВМ с заранее подобранными входными данными, и полученные результаты сравнивают с заранее известными правильными результатами (подсчитанными для этих входных данных вручную). Это – тест (проверяющая задача): алгоритм + данные + контрольный пример. Такое тестирование желательно повторить несколько раз.

    Если  результат совпадает с известным, это дает некоторые основания  считать программу верной. Даже при  хорошем тестировании  в программе  могут остаться ошибки. Для того, чтобы рассеять все сомнения, нужно выполнить все возможные варианты (то есть провести расчет со всеми возможными входными данными). Например, нужно сложить два числа из 10 цифр каждое. Тогда нам придется проверить 10²⁰ вариантов. Это практически невозможно, хотя бы по следующим причинам.

    Пусть одна операция сложения выполняется  за 1 мкс = 10^-6 с. Тогда

          10²⁰*10^-6=10¹⁴ с,

          10¹⁴/60 ≈ 1.7*10¹² мин.,

          ≈ 2.78*10¹⁰ час.,

          ≈1.16*10⁹ суток,

          ≈3.17*10⁷ лет = 31 700 000 лет.

    На  основе подобных рассуждений Э. Дейкстра (голландский профессор, классик  современного программирования) сформулировал  такой закон (закон Дейкстры):

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

         Чтобы убедиться в правильности  программы, отсутствии в ней  алгоритмических ошибок, нужно уметь проверять правильность структуры алгоритма. Такая аналитическая проверка называется верификацией алгоритма. При использовании этого метода нужно для каждого алгоритма и каждой фразы в нем абстрагироваться от индивидуальных значений переменных и сформулировать условия, которым они должны удовлетворять до и после выполнения алгоритма. Для любого алгоритма можно определить, каким условиям должны удовлетворять входные данные и результат. Это условия подобные тем, которые задаются в операторах IF и WHILE.

    Условие на входе называется предусловием, на выходе – постусловием.

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

    Наиболее  распространенными методами доказательства являются:

• перечисление (перебор вариантов) – для IF-THEN-ELSE и последовательных алгоритмов;
• математическая индукция – для WHILE-DO.

        Проиллюстрируем использование  метода перебора вариантов на  примере алгоритма дихотомии.  Входные данные: C, D, EPS. (функция f – фиксирована и не относится к входным данным).

    Предусловие:

(D>0) AND (EPS>0) AND (f (C-D)*f (C+D) ≤ 0).            (*)

    Постусловие:

(D <= EPS) AND (EPS >0) AND (D>0) AND (f (C-D)*f (C+D) ≤ 0).       (**)

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

    Алгоритм:

    WHILE D>EPS DO

    BEGIN

IF f (C)*f(C+D) >0

          THEN C:=C-D/2

          ELSE C:=C+D/2;

          D:=D/2

    END;

    Пусть выполняется условие

      f (C)*f (C+D) >0.                                                                                   (2)

    Тогда в результате одного выполнения цикла  получим новые значения C_нов и D_нов:

    C_нов = C - D/2,

    D_нов = D/2.

    Проверим  постусловие:

 f (C_нов- D_нов)*f (C_нов+ D_нов) = f (C-D/2-D/2)* f (C-D/2+D/2) =

    =f (C-D)*f (C)≤0 (из (*) и (1)).     (3)

    Таким образом мы доказали, что внутри цикла действует предусловие

          (f (C-D)*f (C+D)≤0) AND (D>0)

и такое  же постусловие. Доказательство провели  методом перебора вариантов.

    Выберите  второй вариант условия f (C) *f (C-D) ≤0 и докажите то же самое.

    Доказательство  по методу математической индукции строится на переборе вариантов, зависящих от некоторого натурального числа n, где n=n₀, n₀+1, n₀+2,…,∞.