Использование методов численного интегрирования

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

11

Федеральное агентство связи

Государственное образовательное учреждение высшего профессионального образования

Московский технический университет связи и информатики

Курсовая работа

по информатике

Выполнил: студент группы СС1003

Польских Д.В.

Проверила: Семенова Т.И.

Москва 2012



Оглавление

1. Индивидуальное задание

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

3. Укрупненный алгоритм решения задачи

4. Обоснование методов решения

5. Описание методов решения

6. Схемы алгоритмов

7. Полный программный код проекта

8. Результаты программы

9. Полное решение с помощью пакета MathCad

10. Полный Программный код тестирования

11. Тестирование методов

Вывод

Используемая литература



1. Индивидуальное задание

Вариант 4

Построить таблицу значений при измененении x с шагом h от x=a до x=b. Найти с точностью е максимум интерполяционного многочлена 2й степени выбрав из полученной таблицы соответствующие значения.

Исходные данные:

a	b	h	е
1	4	0.5

2. Постановка задачи:

1. С использованием одного из методов численного интегрирования провести табуляцию функции в заданных пределах изменения параметра х.

2. Выполнить задачу интерполяции, для чего используем узлы интерполяции x0=1, x1=2.5, x2=4 (начало, конец и середину отрезка)

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



3. Укрупненный алгоритм решения задачи

4. Обоснование методов решения

1. Для проведения оптимизации выберем метод дихотомии, т.к. на каждой итерации отрезок неопределенности сократится практически в два раза.

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

2. Для проведения численного интегрирования выберем метод Симпсона, так как он имеет высокую точность, а так же, потому что функция квадратична.

3. Для проведения интерполяции используем формулу Лагранжа:

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

5. Описание методов решения:

Метод дихотомии

Пусть дана функция f(x), унимодальная на отрезке [a;b]. Обозначим a0 = a и b0 = b. Поиск минимума начинают с выбора на отрезке неопределенности [a0;b0] двух симметричных относительно середины точек:

где - параметр метода.

Сравнивая вычисленные в точках 1 и 1 значения функций f(1) и f(1), в силу унимодальности функции можно провести сокращение отрезка неопределенности следующим образом:

1) если f(1) f(1), то x*[a0;1] (Рис.а);

2) если f(1) > f(1), то x*[1;b0] (Рис.b).

а) b)



Если описанную процедуру принять за одну итерацию, то алгоритм поиска минимума можно описать следующим образом. Опишем k+1 итерацию, исходя из того, что k-й отрезок неопределенности найден [ak;bk]:

Вычисляются

Находят значения f(k+1) и f(k+1).

Находят k+1-й отрезок неопределенности по правилу:

если f(k+1) > f(k+1), то x* [k+1;bk],

если f(k+1) f(k+1), то x*[ak;k+1]).

Вычисления проводятся до тех пор, пока не выполнится неравенство

где n - длина n-го отрезка неопределенности.

Заметим, что от итерации к итерации n убывает и при n стремится к величине 2, оставаясь больше этой величины. Поэтому добиться при некотором значении n длины отрезка неопределенности | меньше заданной точности можно лишь выбирая 0</2.

Метод Симпсона

Метод Симпсона заключается в замене подынтегральной функции на отрезке [a,b] интерполяционным многочленом второй степени p2(x), то есть приближение графика функции на отрезке параболой.

Для более точного вычисления интеграла, интервал [a,b] разбивают на N отрезков одинаковой длины и применяют соответствующую замену на каждом из них. Значение исходного интеграла является суммой результатов интегрирования на всех отрезках.

Где n - число точек, m=0.5n

Метод двойного просчета заключается в неявной оценке погрешности при сравнении значений интеграла при длине шага h и h/2.

Где n - коэффициент различный для каждого метода интегрирования (n = 4 для метода Симпсона).

- Значение интеграла при шаге h

- Значение интеграла при шаге h/2

Метод Лагранжа

Общая формула метода Лагранжа

В задании подчеркнуто что необходимо использовать полином 2 порядка. Его формула

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



А сам полином в явном виде:

6. Схемы алгоритмов

Схема алгоритма работы программы решающей задачу численного интегрирования методом Симпсона:



Схема алгоритма метода дихотомии:



Схема алгоритма интерполяция по методу Лагранжа:

дихотомия алгоритм интерполяционный оптимизация



7. Полный программный код проекта

'программный код первой формы

Public Class Form1

Private Sub b1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles b1.Click

Dim a, ee, b, h, x, y As Single

Dim txt As String = ""

a = vinput(tb1)

h = vinput(tb3)

ee = vinput(tb4)

b = vinput(tb2)

_e = ee

FTab2(a, b, h, txt)

voutput(txt, Form2.tb5)

x = Opt(a, b, ee, y, txt)

voutput(txt, Form2.tb5, True)

voutput("xmax=" + Format(x, "0.0000") + " ymax=" + Format(y, "0.0000"), Form2.lb1)

End Sub

Private Sub b2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles b2.Click

Form2.Show()

End Sub

End Class

'программный код модуля

Imports System.Math

Module Module1

Private XY_Arr(,) As Single

Private Num As Integer

Public _e

Public Function vinput(ByVal t As TextBox) As Single

Return CSng(Val(t.Text))

End Function

Public Sub voutput(ByVal s As String, ByRef t As TextBox)

t.Text = s

End Sub

Public Sub voutput(ByVal s As String, ByRef t As TextBox, ByVal add As Boolean)

If add = True Then

t.Text += s

Else

t.Text = s

End If

End Sub

Public Sub voutput(ByVal s As String, ByRef t As Label)

t.Text = s

End Sub

Public Function F(ByVal x As Single) As Single

Return SM(1, x, _e) - 1

End Function

Public Function P(ByVal x As Single) As Single

Return Interp_mod(x, 2)

End Function

Public Function FInt(ByVal x As Single) As Single

Return Pow(Log(x), 2) / x

End Function

Public Function SM(ByVal a As Single, ByVal b As Single, ByVal e As Single) As Single

Dim n As Integer = 2

Dim cc, i As Integer

Dim h As Single = (b - a) / n

Dim s As Single = (FInt(a) + 4 * FInt((a + b) / 2) + FInt(b)) * h / 3

Dim s1, x As Single

Do

n *= 2

h = (b - a) / n

s1 = s

cc = 4

x = a

s = FInt(a) + FInt(b)

For i = 1 To n - 1

x += h

s += cc * FInt(x)

cc = 6 - cc

Next

s *= h / 3

Loop Until Abs(s - s1) / 15 < e

Return s

End Function

Private Function Interp(ByVal x As Single, ByVal k As Integer, ByVal c(,) As Single) As Single

Dim i, j As Integer

Dim L, L1 As Single

L = 0

For i = 0 To k

L1 = 1

For j = 0 To k

If i <> j Then

L1 *= (x - c(j, 0)) / (c(i, 0) - c(j, 0))

End If

Next j

L += L1 * c(i, 1)

Next i

Return L

End Function

Public Function Interp_mod(ByVal x As Single, ByVal k As Integer) As Single

Dim c(k, 1) As Single

Dim f, i, j, d, l As Integer

Dim h As Single = XY_Arr(1, 0) - XY_Arr(0, 0)

For i = 0 To Num

If (x - XY_Arr(i, 0) < h) Then

f = i

Exit For

'Else

' f = i

End If

Next

i = 0

j = 0

l = 0

While i <= k

d = f - Pow(-1, l) * j

If (Not (d < 0 Or d > Num)) Then

c(i, 0) = XY_Arr(d, 0)

c(i, 1) = XY_Arr(d, 1)

i += 1

End If

If (l Mod 2 = 0) Then j += 1

l += 1

End While

Return Interp(x, k, c)

End Function

Public Sub FTab2(ByVal a As Single, ByVal b As Single, ByVal h As Single, ByRef txt As String)

Dim i As Integer

Dim n As Integer = (b - a) / h

Dim y, yt, x As Single

Num = n

ReDim XY_Arr(Num, 1)

For i = 0 To Num

XY_Arr(i, 0) = a + i * h

XY_Arr(i, 1) = F(XY_Arr(i, 0))

Next

txt = "i" + Space(12) + "x" + Space(17) + "P2(x)" + Space(17) + "yt" + Space(17) + "dy" + vbNewLine

For i = 0 To n

x = XY_Arr(i, 0)

y = P(x)

yt = XY_Arr(i, 1)

txt += Format(i, "00") + Space(6) + Format(x, "0.0000") + Space(6) + Format(y, "0.0000") + Space(6) + Format(yt, "0.0000") + Space(6) + Format(yt - y, "0.0000") + vbNewLine

Next

End Sub

Public Function Optimization_Dih(ByVal a As Single, ByVal b As Single, ByVal E As Single, ByRef y As Single, ByRef t As String) As Single

Dim d, x1, x2 As Single

t = "Оптимизация:" + vbNewLine

t += "a" + Space(15) + "b" + Space(15) + "x1" + Space(15) + "x2" + Space(15) + "y1" + Space(15) + "y2" + Space(15) + "l" + vbNewLine

d = 0.1 * E

Do

x1 = (a + b - d) / 2

x2 = (a + b + d) / 2

t += Format(a, "0.0000") + Space(6) + Format(b, "0.0000") + Space(6) + Format(x1, "0.0000") + Space(6) + Format(x2, "0.0000") + Space(6)

t += Format(P(x1), "0.0000") + Space(6) + Format(P(x2), "0.0000") + Space(6) + Format(b - a, "0.0000") + vbNewLine

If (-P(x1)) > (-P(x2)) Then

a = x1

Else

b = x2

End If

Loop Until Abs(b - a) <= E

t += Format(a, "0.0000") + Space(6) + Format(b, "0.0000") + Space(6) + Format(x1, "0.0000") + Space(6) + Format(x2, "0.0000") + Space(6)

t += Format(P(x1), "0.0000") + Space(6) + Format(P(x2), "0.0000") + Space(6) + Format(b - a, "0.0000") + vbNewLine

x1 = (a + b) / 2

y = P(x1)

Return x1

End Function

End Module



8. Результаты программы

9. Полное решение с помощью пакета MathCad 14

Табуляция функции(интегрирование)

Интерполяция

нахождение максимума



10. Полный программный код тестирования

Imports System.Math

Public Class Form3

Dim XY_Arr(,) As Single

Dim Num As Integer

Dim a, b, EE As Single

Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click

End

End Sub

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

Dim m As String = ""

Dim a, b, EE As Double

vvod(TextBox6, a)

vvod(TextBox5, b)

vvod(TextBox3, EE)

Simpsontest(a, b, EE, m)

vyvod(m, TextBox2)

End Sub

Function Simpsontest(ByVal a As Single, ByVal b As Single, ByVal E As Single, ByRef t As String) As Single

Dim h, S1, x, S As Single

Dim n, c, i As Integer

t = ""

n = 2

h = (b - a) / n

S = (ftest(a) + 4 * ftest((a + b) / 2) + ftest(b)) * h / 3

Do

n = 2 * n

h = (b - a) / n

S1 = S

c = 4

x = a

S = ftest(a) + ftest(b)

For i = 1 To n - 1

x = x + h

S = S + c * ftest(x)

c = 6 - c

Next

S = S * h / 3

t = t + Space(2) + "h=" + Format(h, "0.0000") + Space(6) + "S1=" + Format(S1, "0.0000") + Space(6) + "S=" + Format(S, "0.0000") + Space(6) + "n=" + CStr(n) + vbNewLine

Loop Until Abs(S - S1) / 15 <= E

t = t + vbNewLine

t = t + Space(2) + "h=" + Format(h, "0.0000") + Space(6) + Space(6) + "S=" + Format(S, "0.0000") + Space(6) + "n=" + CStr(n) + vbNewLine

Return S

End Function

Private Sub Button5_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button5.Click

Dim x0, ee, b, x, y As Single

Dim txt3 As String

txt3 = ""

x0 = vinput(TextBox8)

ee = vinput(TextBox1)

b = vinput(TextBox7)

x = Optimization_Dih1(x0, b, ee, y, txt3)

voutput(txt3, TextBox4)

voutput("xmax=" + Format(x, "0.000") + " ymax=" + Format(y, "0.000"), Label13)

End Sub

Public Function Optimization_Dih1(ByVal a As Single, ByVal b As Single, ByVal E As Single, ByRef y As Single, ByRef t As String) As Single

Dim d, x1, x2 As Single

t = "a" + Space(15) + "b" + Space(15) + "x1" + Space(15) + "x2" + Space(15) + "y1" + Space(15) + "y2" + Space(15) + "l" + vbNewLine

d = 0.1 * E

Do

x1 = (a + b - d) / 2

x2 = (a + b + d) / 2

t += Format(a, "0.0000") + Space(6) + Format(b, "0.0000") + Space(6) + Format(x1, "0.0000") + Space(6) + Format(x2, "0.0000") + Space(6)

t += Format(Fd(x1), "0.0000") + Space(6) + Format(Fd(x2), "0.0000") + Space(6) + Format(b - a, "0.0000") + vbNewLine

If (-Fd(x1)) > (-Fd(x2)) Then

a = x1

Else

b = x2

End If

Loop Until Abs(b - a) <= E

t += Format(a, "0.0000") + Space(6) + Format(b, "0.0000") + Space(6) + Format(x1, "0.0000") + Space(6) + Format(x2, "0.0000") + Space(6)

t += Format(Fd(x1), "0.0000") + Space(6) + Format(Fd(x2), "0.0000") + Space(6) + Format(b - a, "0.0000") + vbNewLine

x1 = (a + b) / 2

y = Fd(x1)

Return x1

End Function

Public Function Fd(ByVal x As Single) As Single

Return -(x ^ 2) + 1

End Function

Private Sub Button4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click

Dim a, k, h, b As Single

a = vinput(tb31)

k = vinput(tb34)

h = vinput(tb33)

b = vinput(tb32)

voutput(Interp_test(a, b, h, k), tb35)

End Sub

Public Function Interp_test(ByVal a As Single, ByVal b As Single, ByVal h As Single, ByVal k As Integer) As String

Dim txt As String

Dim i As Integer

Dim yt, y, x As Single

Num = (b - a) / h + 1

ReDim XY_Arr(Num, 1)

For i = 0 To Num - 1

XY_Arr(i, 0) = a + h * i

XY_Arr(i, 1) = XY_Arr(i, 0) * XY_Arr(i, 0)

Next

txt = "i" + Space(12) + "x" + Space(17) + "y" + Space(17) + "L" + Space(17) + "y-L" + vbNewLine

h /= 2

Dim n As Integer = (b - a) / h + 1

For i = 0 To n - 1

x = a + h * i

y = Filt(x)

yt = Interp_mod1(x, k)

txt += Format(i, "00") + Space(6) + Format(x, "0.0000") + Space(6) + Format(y, "0.0000") + Space(6) + _

Format(yt, "0.0000") + Space(6) + Format(y - yt, "0.0000") + vbNewLine

Next

Return txt

End Function

Public Function Interp1(ByVal x As Single, ByVal k As Integer, ByVal c(,) As Single) As Single

Dim i, j As Integer

Dim L, L1 As Single

L = 0

For i = 0 To k

L1 = 1

For j = 0 To k

If i <> j Then

L1 *= (x - c(j, 0)) / (c(i, 0) - c(j, 0))

End If

Next j

L += L1 * c(i, 1)

Next i

Return L

End Function

Public Function Interp_mod1(ByVal x As Single, ByVal k As Integer) As Single

Dim c(k, 1) As Single

Dim f, i, j, d, l As Integer

Dim h As Single = XY_Arr(1, 0) - XY_Arr(0, 0)

For i = 0 To Num - 1

If (x - XY_Arr(i, 0) < h) Then

f = i

Exit For

End If

Next

i = 0

j = 0

l = 0

While i <= k

d = f - Pow(-1, l) * j

If (Not (d < 0 Or d > Num - 1)) Then

c(i, 0) = XY_Arr(d, 0)

c(i, 1) = XY_Arr(d, 1)

i += 1

End If

If (l Mod 2 = 0) Then j += 1

l += 1

End While

Return Interp1(x, k, c)

End Function

Public Function Filt(ByVal x As Single) As Single

Return x * x

End Function

Function ftest(ByVal x As Single) As Single

Return x ^ 2

End Function

Public Sub vvod(ByVal t As TextBox, ByRef x1 As Single)

x1 = CSng(Val(t.Text))

End Sub

Public Sub vyvod(ByVal l As String, ByRef t As TextBox)

t.Text = l

End Sub

End Class



11. Результаты тестирования

Тест интегрирования:

Точность	S
0.001	9

Решение в MathCad 14:

Тестирование метода дихотомии:



Точность	Xmax	Ymax	a-b
0.1	-0.031	0.999	0.0723
0.01	-0.004	1.000	0.0088
0.001	0.000	1.000	0.0006

Проверка в пакете MathCad 14: (можно обходится и без проверки, т.к. пример простой и ответ можно посчитать в уме)

Тест интерполяции по Лагранжу:



L точно повторяет функцию, подобранную для теста, разница между ними отсутствует, следовательно процедура работает верно.

к - степень интерполяционного многочлена, т.е. строит по 3м точкам



Вывод

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

,

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



Используемая литература

1. Кравченко О.М., Семенова Т.И., Шакин В.Н. «Модели решения задач Численные методы и оптимизация» 2003 г.

2. Гловацкая А.П., Загвоздкина А.В., Кравченко О.М. «Практикум. Численные методы и оптимизация по дисциплине “Информатика”» 2004 г.

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