программы_вычмат. Контрольная работа 1 по дисциплине Вычислительная математика учебное пособие Мицель А. А. Вычислительная математика

• Название: Контрольная работа 1 по дисциплине Вычислительная математика учебное пособие Мицель А. А. Вычислительная математика
• Дата: 03.06.2022
• Размер: 451.5 Kb.
• Имя файла: программы_вычмат.doc
• Тип: Контрольная работа; #566727
• страница: 1 из 2

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

Томский государственный университет систем управления и

радиоэлектроники

Кафедра автоматизированных систем управления (АСУ)

Контрольная работа №1

по дисциплине «Вычислительная математика»

учебное пособие Мицель А.А. «Вычислительная математика»

Вариант №15

Выполнил студент

специальности 090301

Корякин Станислав Вячеславович

06.12.2016

г. Советский 2016

Содержание

1 Решение уравнений с одной переменной 4

1.1 Задание 4

1.2 Теоретические сведения 5

1.3 Результаты работы программы 5

2 Решение задач линейной алгебры 7

2.1 Решение систем линейных уравнений 7

2.1.1 Задание 7

2.1.2 Теоретические сведения 7

2.1.3 Результаты работы программы 10

2.2 Вычисление определителей матриц 10

2.2.1 Задание 10

2.2.2 Теоретические сведения 11

2.2.3 Результаты работы программы 11

2.3 Вычисление обратной матрицы 11

2.3.1 Задание 11

2.3.2 Теоретические сведения 12

2.3.3 Результаты работы программы 12

3 Приближение функций 14

3.1 Задание 14

3.2 Теоретические сведения 14

3.3 Результаты работы программы 16

4 Численное дифференцирование 18

4.1 Задание 18

4.2 Теоретические сведения 18

4.3 Результаты работы программы 20

5 Численное интегрирование 22

5.1 Задание 22

5.2 Теоретические сведения 22

5.3 Результаты работы программы 24

Приложение 25

1 Решение уравнений с одной переменной

1.1 Задание

Написать программу отделения корней.

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

а) методом перебора;

б) методом дихотомии;

б) методом хорд;

в) методом золотого сечения;

г) методом Ньютона;

д) методом итераций;

е) комбинированным методом.

Входные данные:

• 
  функция f(х) и ее первая и вторая производные (для метода Ньютона, итераций и комбинированного метода);
  
• 
  интервал [a,b];
  
• 
  точность ε₁, ε₂;
  
• 
  метод.
  

Выходные данные:

• 
  корни ξ_i, точность;
  
• 
  значения функции f(ξ_i);
  
• 
  количество итераций n;
  
• 
  количество вычислений функции f(x);
  
• 
  время счета;
  
• 
  параметр сходимости
  

1.2 Теоретические сведения

Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Легко доказать, что золотое сечение отрезка [a; b] производится двумя точками y и z, симметричными относительно середины отрезка.

λ Δ

λ Δ (λ – 1)Δ

с d

a b

(λ – 1)Δ Δ


Отсюда

c = (λ – 1)a + (λ – 1)²b = 0,618 a + 0,382 b.

d = (λ – 1)²a + (λ – 1)b = 0,382 a + 0,618 b.

Нетрудно также проверить, что точка c производит золотое сечение отрезка [a; d], а точка d производит золотое сечение отрезка [c;b]. На этом свойстве, позволяющем на каждой итерации вычислить значение функции лишь в одной пробной точке, и основан алгоритм метода золотого сечения.

Алгоритм:

1)

c=b-d+a

2) если f(a)*f(d)<0, то b=d, иначе a=c

3) x=(a+b)/2

4) если (b-a)<2 и |f(x)|< , возврат к шагу 1, иначе результат найден (х)
1.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.1.



Рисунок 1

2 Решение задач линейной алгебры

2.1 Решение систем линейных уравнений

2.1.1 Задание

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

а) методом Гаусса;

б) методом ортогонализации;

в) методом Халецкого;

г) методом простой итерации;

д) методом Зейделя.

Входные данные:

- порядок системы n ;

- матрица системы A;

- правая часть системы b;

- точность ε (для итерационных методов);

- метод.

Выходные данные:

- решение системы;

- невязка.



2.1.2 Теоретические сведения

Метод Гаусса состоит из двух этапов: прямого хода и обратного хода. На первом этапе (прямой ход) матрица приводится к треугольному виду. Рассмотрим систему:



Предположим, что элемент первой строки, расположенный на главной диагонали не равен нулю: a₁₁0. Исключим x₁ из второго уравнения. Для этого умножим первое уравнение на s₂₁=-а₂₁/а₁₁ и сложим со вторым. В итоге получим:



где элементы второй строки вычисляются по формуле



Естественно решение системы не изменится.

Исключим x₁ из третьего уравнения. Для этого умножим первое на s₃₁=-a₃₁/a₁₁ и сложим с третьим. В результате в третьей строке получим элементы

,

при этом элемент первого столбца .

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



при этом новые элементы вычисляются по формулам:



где s_j1=-a_j1/a₁₁.

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



где



Формулы (11) являются общим алгоритм исключения j - той строки и k - го столбца метода Гаусса. Они получены из формулы исключения 1 - го столбца заменой индекса 1 на индекс k.

Обратный ход состоит в вычислении искомых величин. Из последнего уравнения определяется значен6ие и это значение переносится в правую часть уравнения (значение заменяется на значение x_n). Далее подставляем x_n в (n-1) ое уравнение и определяем x_n-1 и т.д. до x₁. Таким образом, полученное решение будет находиться в столбце свободных членов.

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

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

Оценим количество операций. При исключении x₁ из 2 – го уравнения мы делаем (n+1) умножений и (n+1) сложений, т.е. 2(n+1) операций. Следовательно, для исключения из всех строк (таких строк n-1) необходимо выполнить N₁=2(n+1)(n-1)=2(n²-1)2n² операций. На следующем этапе N₂2(n-1)² и т.д. Общее количество операций равно:

NN₁+N₂+…+N_n=2n²+2(n-1)²+…+22n³/3.

Метод Гаусса уже при n=2 имеет преимущество по сравнению с правилом Крамера, не говоря уже о больших n.

Если матрица сводится не к треугольному, а диагональному виду, то такая модификация метода Гаусса называется методом Жордана-Гаусса. Он требует 2n³ операций и обычно применяется для нахождения обратных матриц.

2.1.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.2.

Входные данные:



Выходные данные:



Рисунок 2

2.2 Вычисление определителей матриц

2.2.1 Задание

Написать программу вычисления определителя матрицы одним из следующих методов:

а) методом Гаусса;

б) методом декомпозиции.

Входные данные:

- порядок системы n ;

- матрица системы A;

- метод.

Выходные данные:

- значение определителя.

2.2.2 Теоретические сведения

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

Это обусловлено тем, что при сложении (вычитании) строк определитель не меняется; при умножении строки на число определитель также увеличивается в то же число раз.

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

2.2.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.3.

Входные данные:



Выходные данные:



Рисунок 3

2.3 Вычисление обратной матрицы

2.3.1 Задание

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

а) методом Гаусса;

б) методом ортогонализации;

в) методом Халецкого.

Входные данные:

- порядок системы n ;

- матрица системы A;

- метод.

Выходные данные:

- обратная матрица;

- произведение прямой и обратной матрицы.

2.3.2 Теоретические сведения

Преобразования для получения обратной матрицы аналогичны описанным в п.2.1 – с тем отличием, что к основной матрице системы присоединяется не вектор-столбец свободных членов, а единичная матрица. После преобразований на месте единичной матрицы получаем обратную матрицу:



Согласно свойству обратной матрицы, AA^-1=A^-1A=E.
2.3.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.4.

Входные данные:



Выходные данные:



Рисунок 4

3 Приближение функций

3.1 Задание

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

Входные данные:

- исходная сетка узлов интерполяции;

- значения интерполируемой функции;

- новая сетка узлов, на которой необходимо вычислить значения функции;

- порядок полинома;

- метод.

Выходные данные:

- новая сетка;

- значения функции на новой сетке;

- погрешность интерполирования.



3.2 Теоретические сведения

Многочлен Лагранжа ищется в виде линейной комбинации из значений f(х) в узлах интерполяции и каких-то специально построенных из системы узлов интерполяции многочленов n-ой степени в виде:

.

Итак, сначала строится вспомогательный многочлен (n+1)-й степени



и многочленn-й степени

.

Очевидно, что многочлен (n+1) степени обращается в нуль в узлах интерполяции x_i, т.е. (x_i) = 0, i = , а многочлен n-й степени _i(x) обращается в ноль во всех узлах, кроме узла x_i, т.е.:



Таким образом, построенный новый многочлен



принимает нулевое значение во всех узлах, кроме j-го, а в узле x_j его значение будет равно единице, т.е.

.

Тогда j-й многочлен из l_j(x_i)  y_j будет принимать нулевые значения во всех узлах, кроме x_j, и значение y_j в узле x_j, т.е.



Составим многочлен

,

где .

Или в более свернутой форме

;

Его погрешность , где   [a, b].

Если величина h = x_i+1 – x_i = const, тогда произвольный узел x_i = x₀+ih, . Введем переменную t = (x – x₀)/ h. Тогда

x – x_i = x₀ + th – x₀ – ih = (t – i)h .

Подставив разности в , определенную выше, получим:

.

Далее, так как

x_j– x_i = (x₀ + jh) – (x₀ + ih) = (j – i)h,

то формула Лагранжа примет вид:

,

где t = (x – x₀)/h.

Его погрешность .

3.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.5 и рис. 6.



Рисунок 5



Рисунок 6

4 Численное дифференцирование

4.1 Задание

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

Входные данные:

- исходная сетка узлов функции;

- значения дифференцируемой функции;

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

- тип полинома;

- порядок полинома.

Выходные данные:

- новая сетка;

- значения производных функции на новой сетке;

- порядок полинома;

- погрешность дифференцирования (для полинома Ньютона).



4.2 Теоретические сведения

Запишем интерполяционный многочлен Лагранжа L(x) и его остаточный член R_L(x) для случая трех узлов интерполяции (n= 2), но с учетом, что x_i – x_i–1 = h = const (i = 1,2, ..., n):

L(x) = [(x – x₁)(x – x₂)y₀ – 2(x – x₀)(x – x₂)y₁ + (x – x₀)(x – x₁)y₂];

R_L(x) = (x – x₀)(x – x₁)(x – x₂).

Найдем их производные:

L'(x) = [(2x – x₁ – x₂)y₀ – 2(2x – x₀ – x₂)y₁ + (2x – x₀ – x₁)y₂];

R'_L(x) = [(x – x₁)(x – x₂) + (x – x₀)(x – x₂) + (x – x₀)(x – x₁)].

Здесь – значение производной в некоторой внутренней точке x_  [x₀,x_n].

Запишем выражение для производной y'₀ при х = x₀:

y'₀ = L'(x₀) + R'_L(x₀) = [(2x₀ – x₁ – x₂)y₀ – 2(2x₀ – x₀ – x₂)y₁ +

+ (2x₀ – x₀ – x₁)y₂] + [(x₀ – x₁)(x₀ – x₂) + (x₀ – x₀)(x₀ – x₂) + (x₀ – x₀)(x₀ – x₁)] =

= (– 3y₀ + 4y₁ – y₂) + .

Аналогично можно получить значения y'₁, y'₂ при х = x₁, х = x₂.

Итак, для случая трех узлов (n= 2) рабочие формулы имеют следующий вид:







В справочных пособиях приведены формулы Лагранжа для n = 3,4, …. Так для случая четырех узлов (n = 3):









Можно утверждать, что, используя значения функции в (n+1) узлах, получают аппроксимацию n-го порядка точности для производной. Эти формулы можно использовать не только для узлов x₀, x₁, x₂, …, но и для любых узлов x= x_i, x_i+1, x_i+2, … с соответствующей заменой индексов. С помощью многочлена Лагранжа получены аппроксимации и для старших производных.

Таким образом, при n=2:







при n= 3:







и т.д.
4.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.7.



Рисунок 7

5 Численное интегрирование

5.1 Задание

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

Входные данные:

- начальное количество узлов n₀;

- сетка узлов (или шаг сетки и границы интервала);

- значения функции либо аналитическая функция;

- метод интегрирования;

- относительная точность.

Выходные данные:

- значение интеграла;

- количество узлов.

2) Написать программу вычисления интеграла по формуле Гаусса с автоматическим выбором шага интегрирования.

Входные данные:

- порядок формулы;

- границы интервала;

- подынтегральная функция;

- относительная точность.

Выходные данные:

- значение интеграла;

- количество узлов.



5.2 Теоретические сведения

Чтобы получить формулу Симпсона, применим параболическую интерполяцию на отрезке [x_i-1, x_i+1]. Используя многочлен Лагранжа 2 - ой степени имеем интерполяционный многочлен:



Следовательно можем записать:



Для всего отрезка [a, b] соответственно получаем:



Квадратурная формула Гаусса основана на использовании полиномов Лежандра:



где t_i – нули полиномов Лежандра степени n.

n	i	ti	Ai
1	1	0	2
2	1;2	0.57735027	1
3	1;3 2	0.77459667 0	5/9 8/9
4	1;4 2;3	0.86113631 0.33998104	0.34785484 0.65214516
5	1;5 2;4 3	0.90617985 0.53846931 0	0.23692688 0.47862868 0.56888889
6	1;6 2;5 3;4	0.932469515 0.66120939 0.23861919	0.17132450 0.36076158 0.46791394

Критерий останова:



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

5.3 Результаты работы программы

Листинг программы представлен в Приложении.

Результат работы программы представлен на рис.8.



Рисунок 8

Приложение