Объектно-ориентированное программирование на примере численных методов

Объектно-ориентированное программирование на примере численных методов

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

Подобные задачи решаются с помощью численных методов, разработанных для решения математических задач при помощи вычислительной техники на таких языках программирования, как: QBASIC, TURBO PASCAL, C++, DELPHI, VISUAL BASIC и д.р. пакеты программ. В частности, математические пакеты MathCAD, Maple, MathLab также дают возможность решения аналогичных задач.

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

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

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

1. Постановка задач

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

Составить программу приближённого вычисления алгебраических и трансцендентных уравнений методом хорд 2х-3sin (2x) — 1=0 и описать выше указанный метод, составить блок-схему, описать стандартные и не стандартные функции, применяемые в задаче, описать интерфейс и привести пример.

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

Составить программу для решения дифференциальных ур-й методом Рунге-Кутта.

шаг 0.1

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

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

2.1 Метод хорд

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

В зависимости от того, лежат ли точки и по разные стороны от корня или же по одну и ту же сторону, получаем такие чертежи:

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

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

построенному для отрезка между и, график которой проходит через точку :

Решая уравнение, находим то есть

(1)

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

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

Имеются две разновидности применения формулы (1).

Первая разновидность: вычисления ведутся непосредственно по формуле (1) при, начиная с двух приближений и, взятых, по возможности, поближе к корню. При этом не предполагается, что лежит между и (и что значения функции в точках и имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между и на каком-либо следующем шаге (хотя это и не исключено). В таком случае затруднительно дать оценку погрешности, с которой приближает истинное значение корня, и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство, гдежелаемая точность нахождения корня. При этом полагают приближённое значение корня равным[1].

2.2 Решение систем линейных уравнений методом Зейделя

Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений

Ax = b

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

x = Bx + c.

Здесь B — квадратная матрица с элементами b_ij (i, j = 1, 2, …, n), c — вектор-столбец с элементами c_ij (i = 1, 2, …, n).

В развернутой форме записи система имеет следующий вид:

x₁ = b₁₁x₁ + b₁₂x₂ + b₁₃x₃ + … + b_1nx_n + c₁

x₂ = b₂₁x₁ + b₂₂x₂ + b₂₃x₃ + … + b_2nx_n + c₂

…

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_nnx_n + c_n

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x₁:

x₁ = a₁₁-¹ (b₁ — a₁₂x₂ — a₁₃x₃ — … — a_1nx_n),

из второго уравнения — неизвестное x₂:

x₂ = a₂₁-¹ (b₂ — a₂₂x₂ — a₂₃x₃ — … — a_2nx_n),

и т.д. В результате получим систему

x₁ = b₁₂x₂ +b₁₃x₃ + … +b_1,n-₁x_n-₁ +b_1nx_n+ c₁,

x₂ = b₂₁x₁ +b₂₃x₃ + … +b_2,n-₁x_n-₁ +b_2nx_n+ c₂,

x₃ = b₃₁x₁ +b₃₂x₂ + … +b_3,n-₁x_n-₁ +b_3nx_n+ c₃,

…

x_n = b_n1x₁ +b_n2x₂ + b_n3x₃ +… +b_n,n-₁x_n-₁ +c_n,

в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам

b_ij = - a_ij / a_ii, c_i = b_i / a_ii (i, j = 1, 2, …, n, j? i)

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

Введем нижнюю и верхнюю треугольные матрицы

0 0 0 … 0 0 b₁₂ b₁₃…b_1n

b₂₁ 0 0 … 0 0 0 b₂₃…b_2n

B₁ = b₃₁ b₃₂ 0 … 0, B₂ = 0 0 0 … b_3n

… …

b_n1 b_n2 b_n3…0 0 0 0 … 0

Заметим, что B = B₁ + B₂ и поэтому решение x исходной системы удовлетворяет равенству

x = B₁x + B₂ x + c.

Выберем начальное приближение x⁽⁰⁾ = [x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_n⁽⁰⁾]^T. Подставляя его в правую часть равенства при верхней треугольной матрице B₂ и вычисляя полученное выражение, находим первое приближение

x⁽¹⁾ = B₁x⁽⁰⁾ + B₂x⁽¹⁾

Подставляя приближение x⁽¹⁾, получим

x⁽²⁾ = B₁x⁽¹⁾ + B₂x⁽²⁾

Продолжая этот процесс далее, получим последовательность x⁽⁰⁾, x⁽¹⁾, …, x⁽ⁿ⁾, … приближений к вычисляемых по формуле

x^(k+1) = B₁^(k+1) + B₂^(k) + c

или в развернутой форме записи

x₁^(k+1) =b₁₂x₂^(k) + b₁₃x₂^(k) + … +b_1nx_n^(k) + c_1,

x₂^(k+1) =b₂₁x₁^(k+1) +b₂₃x₃^(k) + … +b_2nx_n^(k) + c_2,

x₃^(k+1) =b₃₁x₁^(k+1) +b₃₂x₂^(k+1) +… +b_3nx_n^(k) + c_3,

…

x_n^(k+1) =b_n1x₁^(k+1) +b_n2x₂^(k+1) +b_n3x₃^(k+1) +… +c_n.

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

x_i^(k+1) = x_i^(k) — a_ii-¹(?_j=1ⁱ-¹ a_ijx_j^(k+1) + ?_j=1ⁿ a_ijx_i^(k) — b_i).

Тогда достаточным условием сходимоти метода Зейделя будет

?_{j=1, j?i} ⁿ | a_ij | < | a_ii |

(условие доминированния диагонали).

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений. [2]

2.3 Метод Рунге-Кутта

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

которые имеют решение:

где t — независимая переменная (например, время); X, Y и т. д. — искомые функции (зависимые от t переменные). Функции f, g и т. д. — заданы. Также предполагаются заданными и начальные условия, т. е. значения искомых функций в начальный момент.

Одно дифференциальное уравнение — частный случай системы с одним элементом. Поэтому, далее речь пойдет для определенности о системе уравнений. Метод Рунге-Кутта заключается в рекуррентном применении следующих формул:

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

Блок-схема программы Glav

Блок-схема модуля hord1 (процедура hord)

Блок-схема модуля zeid1 (процедура zeid)

Блок-схема модуля roonge1 (процедура roonge)

3. Описание стандартных функций

Используется процедура Clrscr стандартного модуля Crt. Указанная процедура очищает экран и помещает курсор в его верхний левый угол. Действует процедура следующим образом: все символы заменяются на пробел с атрибутами, установленными в данный момент. Например, если цвет фона TextBackground не черный, то экран будет иметь цвет фона. Процедура выполняется в том окне, в котором она вызвана. Например, в случае

Window (1,1,60,20);

Clrscr;

Будет очищен прямоугольник 60*20, начинающийся в (1,1)

Следующие задействованные всеми создаваемыми модулями процедуры: Write (), Writeln (), Read (), Readln () стандартного модуля System. Объявление этого модуля утилитой Uses не обязательно, он автоматически подключается программными средствами Pascal. Перечисленные операторы являются операторами ввода, вывода. Привлечение этих процедур открывает возможность многократного использования одной и той же программы для вычисления с различными исходными данными.

При выполнении оператора ввода 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 — возвращает считанный символ.

И, наконец, последняя, стандартная функция, используемая только в модуле myiter1. Это функция Abs () — возвращающая абсолютное значение аргумента. Она входит в состав стандартного модуля System. Возвращаемый тип данных тот же, что и у аргумента (real, integer).

Abs (x) — возвращает абсолютное значение х.

4. Описание нестандартных функций

Описание не стандартных функций сводится к описанию модулей.

Модуль hord1 содержит следующие функции и методы:

Funct (x:real):real; - принимает одно входное значение x, после чего функция вычисляет и возвращает значение исходной математической функции от данного x;

Hord.init данный метод инициализирует новый объект типа hord;

Hord.shag данный метод выполняет один математический шах по методу хорд в объекте hord;

Hord.poisk:real данная функция реализует цикл поиска корня линейного уравнения по методу хорд, после окончания поиска функция возвращает значение корня.

Модуль zeid1 — содержит одну процедуру (zeid). Которая выполняет решение системы линейных уравнений методом Зейделя.

Модуль roonge1 — содержит одну процедуру (roonge). Которая выполняет решение дифференциального уравнения методом Рунге-Кутта.

5. Описание интерфейса

Основная программа GLAV (использующая методы структурного программирования) работает следующим образом. Используя способ запроса, определяет дальнейший ход развития. При получении любого результата отличного от 1,2,3 вновь возвращается на начало программы. Тем самым, исключая возможность ошибочного ввода. При получении ответа соответствующего цифрам 1,2,3 передает управление одной из процедур описанных в не стандартных модулях пользователя. При этом выполнение главной программы практически заканчивается за исключением оператора выхода, который выполняется при вводе цифры 4. Управление передается соответственно одному из модулей (hord1, zeid1, roonge1). Каждый из перечисленных модулей по сути своей представляет отдельную программу, являющуюся составной частью другой. Это позволяет в зависимости от выбора пользователя выполнить тот или иной самостоятельный модуль, входящий в главную программу.

При выборе 1 управление передается модулю myzend (процедура zend) выполнение которого приводит к выходу из модуля в главную программу.

Аналогично построены и два других модуля входящих в программу GLAV.

Окно главной программы Результат процедуры hord

Результат процедуы zeid

Результат процедуры roonge

6. Численные примеры

Все выше перечисленное в данной курсовой работе проиллюстрировано на конкретных примерах.

1 Задано алгебраическое уравнение, 2х-3sin (2x) — 1=0, имеющее явно отрицательное значение при, и положительное значение при. При заданной точности вычисления, при решении методом хорд, дает .

Видно из графика, что корень уравнения приблизительно равен 1,3

2 Решение заданной системы линейных уравнений осуществлялся с помощью Maple:

Заключение

В заключение хотелось бы отметить, что методы структурного программирования позволяют более мобильно и качественно проводить работу по модернизации программного обеспечения. Так достаточно усовершенствовать отдельный модуль откомпилировать его и главный модуль, для достижения, желаемого результата. Более того, текст главной программы более читаем, и занимает меньше места. Имеющиеся наработки в отдельных модулях можно использовать в других программах, не задумываясь об их работоспособности. Четко вычерченная структура позволяет яснее представить цели и задачи стоящие перед программистом. Не нужно все время перемещаться по тексту взад и вперед. В любой промежуток времени работы над очень большой программной появляется возможность сконцентрироваться на отдельном модуле. Открывается возможность совместной работы нескольких человек над одной громоздкой программной. Удачно разработанный модуль одного программиста становиться, доступен другим.

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

Список используемой литературы

1. Воробьев Г. Н., Бахвалов Н. С. «Численные методы». М.: Наука, 2006. 231 с.

2. Ефимов А. В., Демидович Б. П. «Линейная алгебра и основы математического анализа». М.: Наука, 2011. 386 с.

3. Бараненков Г. С., Демидович Б. П. «Задачи и упражнения по математическому анализу для ВТУЗОВ». М.: Наука, 2010. 184 с.

4. Абрамов С. А., Зима Е. В. «Начало программирования на языке Паскаль». М.: Наука, 2007. 8 с.

5. Епанешников А. Е., Красильников Ю. И. «Программирование в среде турбо Паскаль». М.: Центр МИФИ СП Диалог, 2008. 3−6 с.

Приложение

Метод хорд:

unit myhord;

interface

uses crt;

type hord=object

a, b, c, cp, eps: real;

constructor init;

procedure shag;

function poisk: real;

end;

function funct (x:real):real;

implementation

function funct (x:real):real;

begin

funct:=2*x-3*sin (2*x) — 1

end;

constructor hord. init;

begin

clrscr;

writeln (' Metod HORD');

write ('Vvedite pogreshnost eps = ');

readln (eps);

write ('Vvedite nachalo otrezka: a = ');

readln (a);

write ('Vvedite konets otrezka: b = ');

readln (b);

cp:=b;

c:=b — (funct (b)*(a-b))/(funct (a) — funct (b));

end;

procedure hord. shag;

begin

if (funct (a)*funct (c)>0)

then a:=c

else b:=c;

cp:=c;

c:=b — (funct (b)*(a-b))/(funct (a) — funct (b));

end;

function hord. poisk:real;

begin

while (abs (c-cp)>eps) do

begin

if (funct (c)=0) then

begin

break;

end

else

begin

shag;

end;

end;

poisk:=c;

end;

end.

Метод Зейделя:

unit Dec_sys;

interface

uses crt;

type

matrix=array [1. 10,1.10] of real;

vector=array [1.10] of real;

TDec_sys=object

n:integer;

procedure Zeidel (a:matrix; b: vector; x: vector; e: real);

procedure Dec_Zeidel;

constructor Init;

destructor Done;

end;

implementation

procedure TDec_sys. Zeidel (a:matrix; b: vector; x: vector; e: real);

var i, j, flag: integer;

s1, s2, s, v, m: real;

begin

flag:=1;

for i:=1 to n do

begin

s:= 0;

for j:=1 to n do

if j<>i then

s:=s+abs (a[i] [j]);

if s>=abs (a[i] [i]) then

flag:=0;

end;

if (flag=1) then

begin

repeat

begin

m:=0;

for i:=1 to n do

begin

s1:=0;

s2:=0;

for j:=1 to i do

s1:=s1+(a[i] [j]*x[j]);

for j:=i+1 to n do

s2:=s2+a[i] [j] * x[j];

v:=x[i];

x[i]:=x[i] - ((1 / a[i] [i])*(s1 + s2 — b[i]));

if (abs (v-x[i]) >m) then

m:=abs (v — x[i]);

end;

end; until (m>=e);

writeln ('ђҐиҐ­ЁҐ бЁбвҐл:');

for i:=1 to n do

writeln ('x', i, '=', x[i]: 5:5);

end

else writeln ('`Ёб⥠­Ґ б室Ёвбп!');

end;

procedure TDec_sys. Dec_Zeidel;

var eps: real;

a:matrix;

b, x: vector;

i, j: integer;

begin

clrscr;

writeln ('ђҐиҐ­ЁҐ бЁбвҐл га ў­Ґ­Ё (c):');

writeln ('a11ъx1+a12ъx2+a13ъx3=b1');

writeln ('a21ъx1+a22ъx2+a23ъx3=b1');

writeln ('a31ъx1+a32ъx2+a33ъx3=b1');

writeln;

write ('‚ўҐ¤ЁвҐ в®з­®бвм: '); readln (eps);

writeln;

writeln ('‚ўҐ¤ЁвҐ н «ҐҐ­вл, а биЁаҐ­­®© ваЁжл бЁбвҐл:');

for i:=1 to n do

begin

for j:=1 to n do

begin

write ('a', i, j, '=');

readln (a[i] [j]);

end;

end;

writeln;

writeln ('‚ўҐ¤ЁвҐ н «ҐҐ­вл бв®"Ўж бў®Ў®¤­ле з «Ґ­®ў:');

for i:=1 to n do

begin

write ('b', i, '=');

readln (b[i]);

end;

for i:=1 to n do

begin

x[i]: =0;

end;

writeln;

Zeidel (a, b, x, eps);

readln;

end;

constructor TDec_sys. Init;

begin

n:=3;

end;

destructor TDec_sys. Done;

begin

clrscr;

end;

end.

Метод Рунге-Кутта:

unit rk;

interface

uses crt;

type TEiler=object

x, y, h, b, dx1, dx2, dx3, dx4, ddx: real;

constructor init;

procedure shag;

procedure poisk;

end;

function proizv (f, g: real):real;

implementation

function proizv (f, g: real):real;

begin

proizv:=g*g-f*f;

end;

constructor TEiler. init;

begin

clrscr;

x:=0;

y:=0.5;

h:=0.1;

b:=1;

end;

procedure TEiler. shag;

begin

dx1:=proizv (x, y);

dx2:=proizv (x+h/2, y+h*dx½);

dx3:=proizv (x+h/2, y+h*dx2/2);

dx4:=proizv (x+h, y+h*dx3);

ddx:=(dx1+2*dx2+2*dx3+dx4)/6;

y:=y+ddx*h;

x:=x+h;

end;

procedure TEiler. poisk;

var f: text;

begin

assign (f, '1.txt');

rewrite (f);

while (x<=b) do

begin

writeln ('x=', x:3:3,' ', 'y=', y:3:3);

writeln (f, x, ' ', y);

shag;

end;

close (f);

end;

end.