Технолгия разработки програмных продуктов

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

                             

Если  теперь преобразовать полученное уравнение, то получится итерационная формула, по которой можно вычислить  y_i+1 , если известно y_i  в точке х_i:

                                     

       Сравнивая формулу Эйлера с общим выражением, полученным ранее, видно, что для  приближённого значения интеграла  в методе Эйлера используется простейшая формула интегрирования – формула  прямоугольников по левому краю отрезка. Суть метода Эйлера заключается в замене функции y(x) на отрезке интегрирования прямой линией, касательной к графику в точке x=x_i. Если искомая функция сильно отличается от линейной на отрезке интегрирования, то погрешность вычисления будет значительной. Ошибка метода Эйлера прямо пропорциональна шагу интегрирования: ошибка ~ h.

       Процесс вычислений строится следующим образом: при заданных начальных условиях x₀ и y₀ можно вычислить 

       Таким образом строится таблица значений функции y(x) с определенным шагом (h) по x на отрезке [x₀, x_N]. Ошибка в определении значения y(x_i) при этом будет тем меньше, чем меньше выбрана длина шага h (что определяется точностью формулы интегрирования).

       При больших h метод Эйлера весьма неточен. Он дает все более точное приближение  при уменьшении шага интегрирования. Если отрезок [xi, xi+1] слишком велик, то каждый участок [xi, xi+1] разбивается на N отрезков интегрирования и к каждому их них применяется формула Эйлера с шагом , то есть шаг интегрирования h берется меньше шага сетки, на которой определяется решение.

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

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

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

         Правильность решения можно легко проверить, подставив эту функцию в исходное уравнение.

1.5 Улучшенный метод Эйлера

       Метод Эйлера для расчёта дифференциальных уравнений имеет небольшую точность расчёта. Как было показано ранее, точность расчёта у него зависит от размера шага линейно, зависимость точности от шага – первой степени. То есть, чтобы увеличить точность в десять раз, надо уменьшить шаг в десять раз. На практике интересуются более совершенными методами. Вопрос стоит так: можно ли увеличить точность на порядок, но при этом сэкономить на количестве вычислений? Да, такие методы есть. Модифицированный метод Эйлера имеет точность второго порядка. В методе Эйлера производная берётся в начале шага и по ней прогнозируется движение системы на конец шага, считая, что во время шага производная неизменна. То есть в течение всего шага производная считается той, какой она была в самом начале шага. Это и есть основной источник неточности. 

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

      Пусть, требуется решить уравнение  y' = f(x, y, t). Идея уточнённого метода Эйлера состоит в том, что производную вычисляют не в  i-ой точке, а между двумя соседними точками: i и i + 1. Данная процедура состоит из следующих шагов:

      1.в  точке i вычисляют значение производной: f(x_i, y_i, t);

      2.делают  пол-шага и вычисляют значение  функции на середине отрезка: y_i + 1/2 = y_i + f(x_i, y_i, t) · Δt/2;

      3.в  точке i + 1/2 вычисляют производную: f(xi + 1/2, yi + 1/2, t + Δt/2);

      4.делается  полный шаг из точки i в точку  i + 1 по значению уточненной производной: yi + 1 =yi + f(xi + 1/2, yi + 1/2, t + Δt/2) · Δt;

      5.значение t увеличивается: t := t + Δt. Вся процедура повторяется сначала.

      На  рисунке показано, какой будет  ошибка, если шаг делается по значению производной, вычисленной в точке i,  как это делается в методе Эйлера. Эта ошибка может быть достаточно велика!  

Рисунок 2 - Движение реальной и расчетной системы

        

       На  рисунке показано, как по значению производной, вычисленной в точке i , делается полшага до точки t + Δt/2  и в этой точке вычисляют новую производную. Касательная в этой точке будет другой.

       Далее переносят линию B обратно в точку t. Это соответствует тому, что  из точки t снова делается, — но уже полный, — шаг Δt до точки t + Δt по направлению, соответствующему линии C. Линия C параллельна B. То есть значение производной в точке t берется искусственно равным производной в точке t + Δt/2. Ошибка расчета  во многих случаях при этом уменьшается. Точность метода Эйлера можно повысить, если воспользоваться для аппроксимации интеграла более точной формулой интегрирования - формулой трапеции.  

       Данная  формула оказывается неявной  относительно yi+1  (это значение есть и в левой и правой части выражения), т.е является уравнением относительно yi+1  , решать которое можно, например, численно, применяя какой-либо итерационный метод. Однако, можно поступить иначе и приблизительно вычислить значение функции в узле i+1 с  помощью обычной формулы Эйлера :

       ,

которое затем использовать при вычислении. Таким образом получается улучшенный метод Эйлера (или его ещё называют метод Эйлера с пересчётом). Для  каждого узла интегрирования производится следующая цепочка вычислений:

                                           

                            

       Благодаря более точной формуле интегрирования, погрешность этого метода пропорциональна  уже квадрату шага интегрирования:                                       Ошибка ~ h2.

Правую  часть дифференциального уравнения вычисляют исходя из известных уже значений. Метод решения дифференциальных уравнений такого типа работает как при положительных приращениях, так и при отрицательных. С помощью так называемого прогноза можно найти вспомогательную величину yi+1.  В качестве прогноза мы принимаем рекуррентную формулу Эйлера. За прогнозом следует коррекция, которая позволяет оценить правую часть дифференциального уравнения между обеими точками. Если применить этот простой метод прогноза и коррекции, то ошибка уменьшается пропорционально h в кубе:                                                     Ошибка ~ h3.

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

2. Язык  Pascal

       В 1970 г. возник еще один новый элегантный язык, который в последующие годы оказал влияние на программистов во всем мире.

       Язык  назывался Паскаль - в честь французского философа и математика XVII в. Блеза  Паскаля, а его автором был  Никлаус Вирт (Niklaus Wirth).

       Он  начал писать Паскаль в 1968 г., когда Хоару так и не удалось воспрепятствовать утверждению Алгола-68. В то время Вирт был профессором информатики в Федеральном техническом университете в Швейцарии (где в первый раз собирался комитет по Алголу-58) и нуждался в инструменте для обучения студентов навыкам программирования.

       Вирта не удовлетворял не только новый Алгол, но и все «ныне используемые основные языки программирования, свойства и конструкции которых зачастую нельзя объяснить логически и убедительно и которые нередко просто оскорбляют здравый смысл». Еще подростком Вирт страстно увлекался конструированием радиоуправляемых моделей самолетов. Это привело к тому, что в 1963 г. он получил степень бакалавра по электротехнике в Калифорнийском университете. Он подошел к разработке языка, как инженер подошел бы к конструированию машины. «Если смотреть на программирование как на проектирование машины, - писал он, - то необходимость точности становится более очевидной». 

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

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

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

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

       Благодаря этому Паскаль особенно удобен для  изучения теории и практики программирования, но не для реальных применений. Например, Паскаль, подобно Алголу, не имеет  в самом формальном языке аппарата ввода и вывода. По мнению Вирта, машинно-зависимые действия, такие, как ввод данных с клавиатуры или запись данных во внешнюю память, не соответствуют логике изучения программирования; компиляторы, написанные для реальных компьютеров, должны иметь особые средства реализации таких возможностей.

       Успех Паскаля намного превысил скромные ожидания Вирта. Коллеги по обе стороны  Атлантического океана приняли его  как средство обучения программированию будущих специалистов по информатике.

       Возможно, самое важное состояло в том, что  Паскаль стал путеводной звездой зарождающегося в то время движения за структурное программирование, которое обрело силу в конце 70-х годов. Оно ставило своей целью пересмотр способа разработки программ, и начало ему было положено публикацией в 1972 г. книги «Структурное программирование» англичанина К.А.Р. Хоара, норвежца О.Дж. Дала и выдающегося голландского специалиста по информатике Эдсгера Дейкстры.

       Упор  на логику. Хотя эту фразу разные программисты могут понимать совершенно по-разному, однако по существу она  характеризует систематический математический подход к созданию программного обеспечения, в частности требует разделения программы на небольшие логически увязанные задачи, как это делается в Паскале.

       Одна  из специфических целей структурного программирования - уменьшение использования так называемых безусловных переходов, или операторов GOTO.