Программирование алгоритмов на примере численных методов

                                                                                                                                                                                    

                    

                                                                                                                                                                                         1

СОДЕРЖАНИЕ

 

Введение	2
1  Постановка задачи	3
2  Математическое описание метода	4
2.1 Метод половинного деления	4
2.2 Метод Крамера	4
2.3 Метод прямоугольников	6
3  Блок-схема программы	7
3.1 Блок-схема модуля1 (процедура polovin )	8
3.2 Блок-схема модуля 2 (процедура kramer)	9
3.2.1 Блок-схема модуля 2 (функция det, op)	10
3.3 Блок-схема модуля 3 (процедура pr)	11
4 Описание стандартных функций	12
5 Описание не стандартных функций	14
5.1 Модуль 1 (процедура polovin)	14
5.2 Модуль 2 (процедура kramer)	14
5.2.1 Модуль 2 (функция op)	15
5.3 Модуль 3 (процедура pr)	16
6 Описание интерфейса	17
7 Численный пример	18
Заключение	27
Список используемых источников	28
Приложение	30

 

 

 

 

 

 

ВВЕДЕНИЕ

 

В настоящее время резко возрос интерес к языкам высокого уровня благодаря возможности использования в научных исследованиях, в технике и экономике вычислительных машин, выполняющих построение некоторых величин в точном соответствии с указанным алгоритмом. Эта возможность привлекательна по той причине, что явления процессы, которые изучают в рамках упомянутых исследований, часто удается описать с помощью понятий математики – функций, систем уравнений, неравенств и для получения конкретных сведений об изучаемых явлениях и процессах надо провести некоторые действия над математическими объектами. Человеку достаточно описать алгоритм необходимых преобразований и вычислений, а сами действия выполнит вычислительная машина.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ПОСТАНОВКА ЗАДАЧИ

 

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

1.1 Составить    программу    приближенного   вычисления    методом половинного деления следующего уравнения с заданной точностью ε =10-4            x2+2x+ln(x)=0. Описать вышеуказанный метод, составить блок-схему программы, описать стандартные и не стандартные функции, применяемые в задаче, описать интерфейс и привести пример.

1.2 Составить    программу для вычисления системы уравнений методом Крамера:

.

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

1.3 Составить программу вычисления определенного интеграла с пределами интегрирования от (а;в) по формуле прямоугольников для функции: и заданным количеством шагов n=20 и точностью ε =10-4   . Описать  вышеуказанный метод, составить блок-схему программы, описать стандартные и не стандартные функции, применяемые в задаче, описать интерфейс и привести пример.

 

 

 

 

 

 

2. Математическое описание  методОВ

 

2.1 Метод  половинного деления

Его ещё называют методом дихотомии. Этот метод решения уравнений отличается от других методов тем, что для него не требуется выполнения условия, что первая и вторая производная сохраняют знак на интервале [a, b]. Метод половинного деления сходится для любых непрерывных функций f(x) в том числе недифференцируемых.

Разделим отрезок [a, b] пополам точкой . Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, c] (Рисунок 1), либо на отрезке [c, b] (Рисунок 2).

Рисунок 1.

Рисунок 2.

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

2.2 Метод Крамера

Пусть нам требуется решить систему линейных алгебраических уравнений

в которой число уравнений равно числу неизвестных переменных и определитель основной матрицы системы отличен от нуля, то есть,  . 
Пусть   - определитель основной матрицы системы, а   - определители матриц, которые получаются из А заменой 1-ого, 2-ого, …, n-ого столбца соответственно на столбец свободных членов:

Основной определитель считается следующим образом:

Аналогично считаются определители матриц, которые получаются из А заменой 1-ого, 2-ого, …, n-ого столбца соответственно на столбец свободных членов. После этого решение системы линейных алгебраических уравнений методом Крамера осуществляется по следующим формулам .

.

 

 

2.3 Метод прямоугольников

Численное интегрирование состоит в нахождении интеграла от

непрерывной функции f(x) по формуле

                                                 ,                                     (2)

где коэффициенты  ank  – действительные числа, а точки  хk принадлежат отрезку   [a, b], k  изменяется от 1 до n.

Вид суммы определяет метод численного интегрирования, а разность - погрешность метода.

Для метода прямоугольников формула примет вид

                                             ,                                            (3)

где , х0=а, xk=xk-1+(i+0,5)h, i=0,1...n-1.

Правая часть формулы прямоугольников является интегральной суммой и при h 0 стремится к данному интегралу. Однако при фиксированном h отличается от соответствующего интеграла на величину Rn(f). По заданной абсолютной погрешности ε подбирается параметр n, при котором выполняется равенство < ε.

 

3. БЛОК-СХЕМА ПРОГРАММЫ.

 

 

 

 

                  

                  3.1 Блок-схема modul 1(процедура polovin)

 

                         

 

3.2 Блок-схема модуля 2(процедура  kramer)

 

3.2.1Блок-схема модуля 2(функция op)

 

 

 

 

 

 

3.3 Блок-схема модуля 3(процедура  pr).

 

 

 

 

 

 

4 ОПИСАНИЕ СТАНДАРТНЫХ ФУНКЦИЙ

 

Разработанная программа использует: Write (), Writeln (), Read (), Readln (). Перечисленные операторы являются операторами ввода, вывода.

При выполнении оператора ввода Read() переменным присваиваются значения исходных данных.

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

С помощью процедур вывода Write() строится последовательность значений, которая является результатом выполнения программы. Параметр, заключенный в круглые скобки   может содержать указания ширины поля и количества десятичных знаков. Выражения вывода могут быть следующих типов: char, integer, real, string, packet string или boolean. Процедура вывода, таким образом, позволяет выделить из всего набора вычисленных значений те, которые служат ответом к решавшейся при выполнении программой задаче.

Процедура Writeln() выполняет процедуру Write(), а затем осуществляет переход в начало следующей строки. Процедуры ввода и вывода часто применяют вместе. Например, для ввода трех чисел и вывода их суммы

Read (a,b,c);

х:= a+b+c;

Write(x);

Последней общей для всех модулей функцией является функция ReadKey, которая считывает символ с клавиатуры . Она описана в стандартном модуле Crt. Возвращаемый тип данных - тип char. Функция ReadKey принимает значение считываемого символа, при этом символ не выводится на экран.

 

 

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

(Под специальными, подразумеваются  функциональные клавиши, клавиши  управления курсором, клавиши, нажатые  одновременно с Alt и т.д.). Первый раз функция ReadKey принимает значения х0, а во второй раз - значение расширенного кода, соответствующего данной специальной клавише. Значение х0 не может быть присвоено ReadKey никаким другим способом. Поэтому если ReadKey =х0 , то следующее значение ReadKey обязательно должно трактоваться как расширенный код. Не смотря на то, что применение функции очень широко, однако чаще всего она используется для задержки программы при отладке. Пример применения функции

Ch: = ReadKey - возвращает считанный символ.

                 

                   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 ОПИСАНИЕ НЕСТАНДАРТНЫХ ФУНКЦИЙ

 

Программа GLAV сама по себе использует нестандартные модули 1, 2, 3, которые также содержат процедуры и функции, выполнение которых приводит к выполнению основной программы. Поэтому описание не стандартных процедур и функций, по сути, сводится к описанию процедур и функций, содержащихся в выше перечисленных модулях.

 

5.1 Модуль1 (процедура polovin)

Процедура polovin  содержит пять внутренних переменных типа real, три из них получают первоначальное значение, используя стандартные процедуры ввода-вывода write-read. В ходе выполнения цикла while происходит проверка модуля разности интервала а и b и данного значения сумма , а также вычисление значений корня уравнения согласно формуле метода половинного деления. Действие цикла прекращается сразу же, как только модуль разности текущего значения х станет меньше допустимой погрешности. Процедура выводит найденное значение на экран монитора. Делает проверку правильности полученного ответа путем подстановки в само уравнение и ожидает нажатия любой клавиши для завершения. Выводимое на экран значение имеет тип real. Выше указанная процедура использует стандартные процедуры и функции (clrscr, write, read, writeln, readkey), стандартные операторы (присвоение) и цикл while.

 

5.2 Модуль 2 (процедура kramer)

Эта процедура использует значительно большее количество внутренних переменных(a,b,vv,pop-массивы real, gop-real, i,j-integer). Кроме того, она использует внутреннюю функцию ор для расчета определения матрицы. Используя стандартные процедуры ввода-вывода, получаем значения коэффициентов при неизвестных и значение равенства.

 

 

Вычисляется главный определитель. Затем, используя цикл for, производится поочередная замена столбца на значение уравнения, вычисление определителя матрицы и возврат замененных столбцов. В результате получаем массив дополнительных определителей и главный определитель. Применяя метод Крамера, получаем значения неизвестных системы уравнений, как частное от деления дополнительного определителя матрицы данного столбца на главный определитель. Выводимые на экран монитора решения системы уравнений имеют тип real. Процедура делает проверку правильности найденных значений путем подстановки их поочередно во все три равенства. Выше указанная процедура использует стандартные процедуры и функции (clrscr, write, read, writeln, readkey) стандартные операторы присвоения и цикл for.

Указанная процедура является универсальной для всех систем уравнений удовлетворяющих правилу Крамера (коэффициенты по главной оси матрицы имеют наибольшие значение модуля по сравнению с остальным коэффициентами уравнения), с числом строк равных 3 и числом столбцов h=3, при изменении константы n на любое другое число делает указанную процедуру универсальной.

Как уже говорилось, выше названная процедура использует свою внутреннюю функцию det() являющуюся так же не стандартной.

 

5.2.1 Модуль 2 (функция op)

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

равен старому коэффициенту матрицы плюс значение вышестоящего коэффициента данной строки умноженного на к, где к равно минус частное

от деления первого не нулевого коэффициента данной строки на выше стоящий коэффициент. Функция, используя цикл for, строит квадратную матрицу, имеющую нули ниже главной оси. Таким образом, значение определителя матрицы будет равно произведению коэффициентов главной оси. Функция det() имеет внутренние переменные i,j,h-типа integer и k,op- типа real. Она использует стандартные операторы присвоения цикл for.