Применение компьютерных технологий для реализации численных методов решения типовых математических задач

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Шахтинский институт (филиал)

Федерального государственного бюджетного образовательного учреждения

высшего профессионального образования

«Южно-Российский государственный технический университет

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине: «Информатика»

Тема работы "Применение компьютерных технологий для реализации численных методов решения типовых математических задач"

Студента

I курса группы 10

Махкамовой И.С

Преподаватель

доц. Бондаренко А.И.

Шахты 2011 г.



Введение

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

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

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

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

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

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



1. Численные методы решения уравнений

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

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

f(x)=0 (1.1)

Задача численного решения уравнения складывается из двух этапов. На первом (этапе отделения корней) необходимо определить интервалы [a,b], в которых заданное уравнение содержит один и только один корень. Справедлива теорема: если непрерывная функция f(x) принимает значения разных знаков на концах отрезка [a,b], т.е. f(a)Ч f(b)<0, то внутри этого отрезка содержится по меньшей мере один корень уравнения f(x)=0. Корень будет заведомо единственным, если производная f'(x) cуществует и сохраняет постоянный знак внутри интервала [a,b]. Рассмотрим способы отделения корней: графический и с помощью таблицы знаков данной функции.

Пусть дано уравнение

x³ - 6x + 2 =0

Составим таблицу знаков функции



f(x)= x³ - 6x + 2.

Х	- Ґ	-3	-1	0	1	3	Ґ
Знак f(x)	-	-	+	+	-	+	+

Следовательно, данное уравнение имеет три действительных корня, лежащих в интервалах (-3,-1), (0,1), (1,3).

Графический способ отделения корней уравнения f(x)=0 заключается в определении точек пересечения графика функции y=f(x) с осью x. Однако на практике часто бывает проще, представив данное уравнение равносильным ему h(x)=g(x), построить графики функций y=h(x) и y=g(x). Тогда искомые корни есть абсциссы точек пересечения этих графиков.

На втором этапе необходимо уточнить значение корня, принадлежащего интервалу изоляции [a,b]. Одним из самых простых способов сужения интервала является метод половинного деления, который заключается в следующем: вычисляем значение функции f(x) в точке x=(a+b)/2 и в качестве нового интервала изоляции корня выбираем ту из двух половинок интервала [a,b], на концах которого функция имеет разные знаки. Этот процесс продолжают до тех пор, пока на каком-то шаге |f(x)|<e, где e - заданная точность нахождения корня.

Рассмотрим ещё один способ уточнения корня - метод итераций или метод последовательных приближений. Пусть дано уравнение (1.1). Заменяя это уравнение равносильным ему

х = j(x), (1.2)

строим последовательность приближенных значений корня

x_n+1 = j(x _n) n=0,1,2,...



где x _o - начальное (нулевое) приближение корня, которое обычно находят графически. Вычисления заканчивают, если на каком-то i-м шаге будет выполняться неравенство |x_i - x_i-1|<e.Достаточные условия сходимости итерационного процесса сформулированы в следующей теореме: если во всех точках интервала [a,b] изоляции корня уравнения (2) производная j'(x) удовлетворяет неравенству |j'(x)|<1, то итерационный процесс сходится независимо от нулевого приближения x₀О[a,b]. Так,

x₁ =j(x₀)

|j'(x₀)|=|j'(1,5)|=|(1,5)²-cos(1,5) -1|<1

при x₀ =1,5. Отметим тот факт, что при использовании метода итераций ошибка округления не накапливается. Общая ошибка округления равна ошибке, возникшей в последней итерации. Причина ясна - каждое новое приближение, включая и предпоследнее, можно рассматривать как начальное.

Одним из эффективных методов уточнения корня является метод Ньютона или метод касательных. Пусть корень уравнения f(x)=0 отделен на отрезке [a,b]. Тогда исходя из начального приближения

получаем последовательность приближений корня

n=0,1,2,.... (1.3)



Вычисления прекращают, если на каком-то i-м шаге будет выполняться неравенство |x_i - x_i-1|<e. Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y=f(x) касательной, пересечение которой оси 0х определяет очередное приближенное значение корня.

Рассмотрим, например, уравнение x² - cos x - 1 = 0 на отрезке [1; 1,5].

Для функции

f(x)= x² - cos x - 1,

f '(x)= 2x - sin x,

f ''(x)= 2 + cos x.

f(1,5)=(1,5)² - cos(1,5) - 1 > 0 и f ''(1,5) = 2 + cos(1,5) > 0, поэтому x₀=1,5.

Последовательность приближений корня определяется формулой (1.3)

Реализация методов итераций и Ньютона на языке QBasic имеет вид:

CLS

PRINT "Нахождение корней уравнения x^2 - 1 - cos(x)=0 методом итерации"



eps = .001

x0 = 1.5

1 :

x1 = SQR(1 + COS(x0))

IF ABS(x0 - x1) < eps THEN PRINT "Корень уравнения равен "; x1: GOTO 2

x0 = x1

GOTO 1

2 :

PRINT

PRINT "Нахождения корней уравнения методом Ньютона"

x0 = 1.5

3 :

x1 = x0 - (x0^2 - 1 - COS(x0)) / (2*x0 + SIN(x0))

IF ABS(x0 - x1) < eps THEN PRINT "Корень уравнения равен "; x1: END

x0 = x1

GOTO 3

Результаты работы программы: 1) Метод итераций: х = 1,176697, 2) Метод Ньютона: х = 1,176502

Рассмотрим последовательность действий для получения решения нелинейного уравнения в среде электронной таблицы MS Excel. Решение можно получить несколькими способами. Рассмотрим метод подбора параметра.

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

1. щёлкнуть мышью по кнопке меню Сервис;

2. в раскрывшемся меню щёлкнуть по строке Параметры…;

3. щёлкнуть по кнопке ОK.

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

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

Уточнение корня уравнения этим способом сводится к следующим действиям.

1. Заданное уравнение преобразовать к виду f(x)=0. Левая часть уравнения и будет той функцией, нуль которой необходимо найти. Например, задано уравнение

x² - cos x - 1 = 0.

Тогда функция, нуль которой предстоит найти, имеет вид

f(x)= x² - cos x - 1.

2. В выбранную ячейку рабочего листа (например, А1) ввести текст x=.

3. В соседнюю справа ячейку (например, в ячейку В1) ввести начальное приближение к корню из заданного отрезка (можно использовать значение левой или правой границы: x₀ = 1.5 ).

4. В ячейку строкой ниже (например, A2) ввести текст f(x)=

5. В соседнюю ячейку (B2) ввести формулу для вычисления значений функции =B1^2-COS(B1)-1. Ссылка в формуле вводится щелчком мыши по ячейке с начальным значением аргумента, то есть по ячейке B1.



6. Щёлкнуть мышью по ячейке с формулой для вычисления значений функции (B2).

7. Щёлкнуть мышью по строке меню Сервис.

8. В раскрывшемся меню щёлкнуть по строке Подбор параметра….

9. В появившемся диалоговом окне Подбор параметра удалить адрес текущей ячейки в окне Установить в ячейке, если он не соответствует адресу ячейки с выражением для вычисления значений функции, и щёлкнуть мышью по ячейке с формулой (B2), в окно Значение: ввести 0 (нуль). Щелкнуть мышью в окне Изменяя значение ячейки: а затем щёлкнуть мышью по ячейке со значением x (B1).

10. Щёлкнуть мышкой по кнопке ОK. Результат получен.

2. Численные методы решения систем уравнений

Пусть дана система двух уравнений с двумя неизвестными

(2.1)

действительные корни которых требуется найти с заданной степенью точности. Число этих корней и их приближенные значения можно установить, построив кривые F(x,y)=0 и G(x,y)=0 и определив координаты их точек пересечения.

Для применения метода итераций систему (2.1) приводят к виду

(2.2)

n=0,1,2... (2.3) где x₀,, y₀ - некоторые начальные приближения.

Справедлива теорема. Пусть в прямоугольнике a Ј x Ј b, c Ј y Ј d имеется одно и только одно решение x=a и y=b системы (2.1). Тогда если в указанном прямоугольнике выполняются условия

(2.4)

то процесс последовательных приближений (2.3) сходится к решению x=a и y=b системы, т.е. и .

Рассмотрим данную систему уравнений

Запишем систему в виде



Из рисунка видно, что данная система имеет единственное решение в области 2 < x < 3, 1 < y < 2.

Условия и выполняются для любых значений х и у, так как -1 Ј siny Ј 1 и -1 Ј cos(x-1)Ј 1. Полагая x₀ = 2,5 и y₀ = 1,5 составим программу, реализующую метод итераций.

CLS

PRINT "Решение системы нелинейных уравнений методом итераций"

eps = .001

x0 = 2.5

y0 = 1.5

1 :

x1 = 2 + SIN(y0)

y1 = 1 - COS(x0-1)

IF ABS(x0 - x1) < eps AND ABS(y0 - y1) < eps THEN PRINT x1, y1: END

x0 = x1

y0 = y1

GOTO 1

Результат работы программы: x = 2.986 y = 1.403

Для проверки полученного результата решим эту систему с помощью ППП “Эврика

COS(X-1)+Y=1

X-SIN(Y)=2

Решение :

Переменные Значения

X = 2.9860212

Y = 1.4033957

3. Интерполирование функций

Пусть функция y=f(x) задана таблицей своих значений {x_i,y_i}. Это означает, что дискретному множеству аргумента {x_i} поставлено в соответствие множество значений функции {y_i} (i=0,1,2,...,n). Эти значения - либо результаты расчетов, либо экспериментальные данные.

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

Итак, определим многочлен

P_n(x)=c₀xⁿ+ c₁x^n-1+ ... + c_n-1x+ c_n

значения которого в точках (x_i) (i=0,1,...,n) совпадают со значениями данной функции, т.е. P_n(x_i) = y_i(x_i). Геометрически это означает, что нужно найти кривую вида y= P_n(x) , график которой проходит через заданное множество точек.

Многочлен P_n(x) называется интерполяционным многочленом. Точки {x_i,y_i} называются узлами интерполяции. Доказано, что в указанной постановке задача интерполирования всегда имеет единственное решение.

Интерполяционные формулы обычно используются при нахождении неизвестных значений f(x) для промежуточных значений аргумента. При этом различают интерполирование - когда x₀ Ј x Ј x _n и экстраполирование, когда x і x _n или x Ј x ₀.

В известном смысле задача интерполирования обратна задаче табулирования функций. Именно при табулировании по аналитическому выражению функции находится таблица её значений, а при интерполяции, наоборот, по таблице значений функции строится её аналитическое выражение.

Поставленная задача отыскания многочлена P_n(x) может быть решена путем различных подходов. Из условия P_n(x_i) = y_i, имеем систему

(i=0,1,2,....,n)

Нахождение искомых коэффициентов сводится к решению системы (n+1) уравнений с (n+1) неизвестными. Эта система имеет единственное решение, если значения x_i отличны друг от друга.

Если эти табличные значения изобразить на координатной плоскости, то, соединив их отрезками прямых, получим ломаную 1-2-3-4. Ставится задача: интерполировать эту табличную зависимость многочленом 3-й степени

(3.1)

т.е. найти такие коэффициенты A,B,C,D чтобы график многочлена прошел через заданные точки.

Эти коэффициенты можно найти из решения системы y(x_i) = y_i ( i=1,2,3,4).



(3.2)

В матричной форме эта система в общем виде для заданной таблицы будет иметь вид

ХЧK=Y:

Матричный способ решения системы линейных уравнений (СЛАУ) достаточно прост. Обе части матричного равенства

ХЧK=Y

умножим слева на обратную матрицу Х ^-1. Получим

Х ^-1X K = X ^-1Y . Т.к.

Х ^-1X =E

где E - единичная матрица (диагональная матрица, у которой по главной диагонали расположены единицы). Тогда решение системы запишется в следующем виде K = X ^-1Y. Т.е. для решения системы (вычисления вектора-столбца K необходимо найти для матрицы X обратную X ^-1 и умножить ее справа на вектор-столбец Y свободных членов.

Решим систему (3.2) с помощью электронных таблиц. Задав матрицы Х и Y (смотри на рабочий лист Excel), воспользуемся функциями Excel. Выделим диапазон A9:D12, начиная с ячейки, содержащей формулу

=МОБР(A2:D5)

Нажмите клавишу F2, а затем нажмите клавиши CTRL+SHIFT+ENTER. Если формула не будет введена как формула массива, единственное значение будет равно -0,16667. Далее выделим диапазон A9:D12 и введем формулу

=МУМНОЖ(A9:D12;F2:F5)

Нажмите клавишу F2, а затем нажмите клавиши CTRL+SHIFT+ENTER. Если формула не будет введена как формула массива, единственное значение будет равно 0,33333.

Решив эту систему, получим искомый многочлен

Рассмотренную задачу можно решить, используя различные компьютерные программы. Существуют различные пакеты прикладных программ (ППП) для решения задач вычислительной математики (EUREKA, DERIVE, MATHCAD, MATLAB и др.).

Приведем пример решения рассматриваемой задачи с помощью ППП “Эврика”

y(x)=A*x^3+B*x^2+C*x+D

y(1)=3

y(2)=6

y(3)=5

y(4)=2

Решение :

Переменные Значения

A = 0.33333333

B = -4.0000000

C = 12.666667

D = -6.0000000

4. Нахождение наибольших и наименьших значений функций

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

1. в ячейку (например, A1) ввести текст x=;

2. в ячейку B1 ввести значение начальной границы (число) заданного отрезка (x=1);

3. в соседнюю ячейку снизу A2 ввести текст y=;

4. в расположенную справа ячейку B2 ввести формулу для вычисления значений функции,

=0,333*B1^3-4*B1^2+12,666*B1-6;

5. щёлкнуть мышью по ячейке с целевой функцией B2;

6. щёлкнуть мышью по кнопке меню Сервис;

7. в раскрывшемся меню щёлкнуть мышью по строке Поиск решения (если этой строки в меню нет, то в этом же меню надо встать на строку Надстройки…, щёлкнуть мышью, установить флажок в окошечке Поиск решения диалогового окна Надстройки и щёлкнуть мышью по кнопке ОK, после чего повторить запуск Поиска решения);

8. в появившемся диалоговом окне Поиск решения выполнить следующие установки:

в окне Установить целевую ячейку: щелчком мыши по ячейке B2 установить абсолютный адрес ячейки с целевой функцией $B$2;

9. для поиска максимума переключатель варианта в диалоговом окне Поиск решения установить максимальному значению, а для минимума переключатель варианта установить минимальному значению. Далее задать ограничения для изменяемой ячейки. Порядок установки ограничений следующий:

· щёлкнуть мышью по кнопке Добавить в диалоговом окне Поиск решения;

· в появившемся окне Добавление ограничения щелчком мыши по ячейке (B1) установить абсолютный адрес изменяемой ячейки в окне Ссылка на ячейку

· в среднем окне выбрать вид ограничения (<=; >=; =);

· в окне Ограничение: ввести значение соответствующей границы x=4 (в решаемой задаче два ограничения x Ј 4);

· после установки ограничения щёлкнуть мышью по кнопке ОK;

· в окне Поиск решения щёлкнуть мышью по кнопке Выполнить.

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

Для изменения (корректировки) ограничения надо выделить строку с ограничением и щёлкнуть мышкой по кнопке Изменить, а затем выполнить корректировку.

Заметим, что если в окне Поиск решения выделить нахождение максимального значения, то нажав кнопку Выполнить, Вы получите максимальное значение функции на отрезке [1,4] x=2,17278327, y=6,05233241.

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

CLS

A = .333: B = -4: C = 12.666: D = -6

min = A + B + C + D

max = min

FOR x = 1 TO 4 STEP .01

y = A * x ^ 3 + B * x ^ 2 + C * x + D

IF y > max THEN max = y: xmax = x

IF y < min THEN min = y: xmin = x

NEXT x

PRINT xmax, max, xmin, min

Результат работы программы: x max = 2,169999, y max = 6,052319,

x min = 3,999997, y min = 1,976011.



Литература

1. Информатика. Базовый курс. /Под ред. С.В. Симоновича. - СПб.: Питер, 2005.

2. Информатика: Практикум по технологии работы на компьютере. /Под ред. Н.В. Макаровой. - М.: Финансы и статистика, 2002.

3. Кайлин В.А., Касаев Б.С. Информатика: Практикум на ЭВМ: Учеб. пособие. - М.: ИНФРА-М, 2001.

4.Аллилуев В.А., Березкин Е.Д., Тютин А.В.: Основы программирования на языке QBasic. Новочеркасск, ЮРГТУ, 2000.

5. Камаев В.А., Костерин В.В.:Технологии программирования. М., Высш. Школа, 2005г.

6. Иванова Г.С.: Основы программирования. М., МГТУ им. Н.Э. Баумана, 2002г.

7.Васильков Ю.В., Василькова Н.Н. Excel. Сборник примеров и задач. -М: Финансы и статистика. 2003.

8. Турчак Л.И. Основы численных методов. -М.: Наука, 1987.

9.Копчёнова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. -М.: Наука. 1972.

Размещено на Allbest.ru

...