Применение программных средств для анализа и обработки данных

Национальный исследовательский  технологический университет

Московский институт стали  и сплавов

Кафедра инженерной кибернетики

Курсовая работа по информатике

по теме:

«Применение программных  средств для анализа и обработки данных»

Студент: Ермакова К.Ю.

Группа: Ф7-11-5

Вариант № 12

Преподаватель: Бесфамильный М. С.

 

 

 

Москва, 2013

 

Содержание

 

1 Теоретическая часть 2

1.1 Решение нелинейных уравнений с одним неизвестным 2

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

1.3       Метод Ньютона (касательных) 3

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

1.5       Задача интерполяции функций 4

1.6       Задачи аппроксимации функций методом наименьших квадратов 5

2 Практическая часть 7

2.1 Задание 1. Решение функции методом Ньютона 7

2.2 Задание 2. Вычисление определенного интеграла методом трапеции 11

2.3      Задание 3. Квадратичное интерполирование 15

2.3 Задание 4. Апроксимация функции методом Гаусса-Жордана 18

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

 

 

1 Теоретическая часть

 

В данной курсовой работе описываются решение нелинейных уравнений с одним неизвестным, численное интегрирование, интерполяция и аппроксимация таблично заданных функций с использованием как алгоритмов программирования на языке С#, так и с использованием математического пакета MathCad и табличного редактора Exсel.

1. Решение нелинейных уравнений с одним неизвестным

 

Пусть задана непрерывная  функция f(x). Требуется найти корни уравнения f(x) = 0. Численное решение уравнения f(x) = 0 распадается на несколько подзадач:

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

Уточнение корня происходит с помощью методов, изложенных ниже

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

 

Рис.1 Метод половинного  деления.

 

Иначе называется методом  дихотомии (бисекций). Пусть задан начальный интервал [x₀, x1], на котором f(x₀)f(x₁) ≤ 0 (т.е. внутри имеется не менее чем один корень). Найдем x₂ = ½ (x₀ + x₁) и вычислим f(x₂). Если f(x₀)f(x₂) ≤ 0, используем для дальнейшего деления отрезок [x₀, x₂], если > 0 – используем для дальнейшего деления отрезок [x₁, x₂], и продолжаем деление пополам.

Итерации продолжаются, пока длина отрезка не станет меньше 2ξ – заданной точности. Тогда середина последнего отрезка даст значение корня с требуемой точностью. В качестве иного критерия можно взять | f(x)| ≤ ξy.

 

1.3 Метод Ньютона (касательных)

 

Пусть x₀ – начальное приближение к корню, а f(x) имеет непрерывную производную. Следующее приближение к корню найдем в точке x₁, где касательная к функции f(x), проведенная из точки (x₀, f₀), пересекает ось абсцисс. Затем точно так же обрабатываем точку (x₁, f₁), организуя итерационный процесс. Выход из итерационного процесса по условию

.

Рис.3. Метод Ньютона

Уравнение касательной, проведенной  из точки (x₀, f₀): y(x) = f /(x₀)(x–x₀) + f(x₀) дает для y(x₁) = 0 следующее выражение:

,                                                                                                                          (1)

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

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

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

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

 

Задача численного интегрирования состоит в замене исходной подинтегральной функции f(x), для которой трудно или невозможно записать первообразную в аналитике, некоторой аппроксимирующей функцией φ(x). Такой функцией обычно является полином

.

То есть:

,                                                                                                                    (2)

где R погрешность метода на интервале интегрирования,

Наиболее известными методами вычисления однократных интегралов являются:

1. Методы Ньютона-Котеса. Здесь φ(x) – полином различных степеней. Сюда относятся метод прямоугольников (степень 0), трапеций (степень 1), Симпсона (полином 2 степени);
2. Сплайновые методы. Здесь φ(x) – кусочный полином с условиями связи между отдельными полиномами посредством системы коэффициентов.

1.5 Задача интерполяции функций

 

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

Пусть на отрезке [a, b] заданы n + 1 точки x₀, x₁, ..., x_n, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках f(x₀) =  y₀, f(x₁) =  y₁, ..., f(x_n) =  y_n. Требуется построить интерполирующую функцию ф(x), принимающую в узлах интерполяции те же значения, что и f(x), т.е. такую, что ф(x₀) = y₀, ф(x₁) = y₁, ..., ф(x_n) = y_n.

Геометрически это означает, что нужно найти кривую y = ф(x) некоторого определенного типа, проходящую через заданную систему точек M_i(x_i, y_i) для i =  . Полученная таким образом интерполяционная формула y = ф(x) обычно используется для вычисления значений исходной функции f(x) для значений аргумента x, отличных от узлов интерполяции. Такая операция называется интерполированием функции f(x). При этом различают интерполирование в узком смысле, когда x  принадлежит интервалу [x₀, x_n], и экстраполирование, когда x  не принадлежит этому интервалу.

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

P_n(x) = a0 x₀+ a1x₁ + a₂x₂ + ... + a_nx_n                                                                                                                                                                         (3)

степени не выше n, такой, что P_n(x₀) = y₀, P_n(x₁) = y₁, ..., P_n(x_n) = y_n.

Наиболее известным интерполяционным многочленом P_n(x) является полином Лагранжа.

Пусть задано n+1 значение функции f(x) в узлах x_j - f_j. .Тогда полином Лагранжа можно представить следующим образом:

ф(х) = P_n(х) = _i (x-x_j)/(x_i-x_j).                                                                                      (4)

В простейшем случае интерполяции предполагается, что зависимость y = f(x) на каждом интервале (x_i, x_i+1) является линейной. Тогда для каждого участка (x_i, x_i+1) в качестве интерполяционной формулы y = ф(x) используется уравнение прямой, проходящей через точки M_i(x_i, y_i) и M_i+1(x_i+1, y_i+1), которое имеет вид

                                                                                                 (5)

Процесс решения задачи интерполирования с использованием формулы (5) включают два этапа: выбор интервала (x_i, x_i+1), которому принадлежит значение аргумента х; собственно вычисление значения y = ф(x) по формуле (5).

 

1.6 Задачи аппроксимации функций методом наименьших квадратов

 

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

Введем непрерывную функцию  φ(x) для аппроксимации дискретной зависимости f(x_i), i = 0…n. Будем считать, что φ(x) построена по условию наилучшего квадратичного приближения, если

                                                                                                  (6)

Рассмотрим случай линейной аппроксимации:

φ(x) = c₀φ₀(x) + c₁φ₁(x) + … + c_mφ_m(x),                                                                                  (7)

где φ₀…φ_m – произвольные базисные функции, c₀…c_m – неизвестные коэффициенты, m < n.

Если известна экспериментальная (исходная) погрешность данных ξ, то выбор числа коэффициентов, то есть величины m, определяется условием:

.                                                                                                                                               (8)

Иными словами, если , число коэффициентов аппроксимации недостаточно для правильного воспроизведения графика экспериментальной зависимости. Если , многие коэффициенты в (7) не будут иметь физического смысла.

Для решения задачи линейной аппроксимации в общем случае следует найти условия минимума суммы квадратов отклонений для (6). Задачу на поиск минимума можно свести к задаче поиска корня системы уравнений

, k = 0…m.                                                                                                                                 (9)

Подстановка (7) в (6), а затем расчет (9) приведет в итоге к следующей системе линейных алгебраических уравнений:

Далее следует решить полученную СЛАУ относительно коэффициентов c₀…c_m. После того как с помощью, например, метода Гаусса найдены коэффициенты c₀…c_m, можно построить аппроксимирующую кривую ф(х) или вычислить координаты заданной точки.

 

2 Практическая часть

1. Задание 1. Решение функции методом Ньютона

 

Условие задачи: Для функции y = F₁(x) = P(x) = x⁵ - 3x⁴ - 77x³ + 111x² + 976x - 1006.5, заданной аналитически на отрезке [-100; 100] и заданной точности Ɛ =0.00001

1. Найти интервалы локализации корней,
2. Проверить аналитически необходимые и достаточные условия
3. Найти все корни уравнения F₁(x) =0 на отрезке [-100; 100] с заданной точностью 0.00001 методом Ньютона.
4. Сделать проверку в Matchcad

 

Решение задачи в С#.

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication2

{

    class Program

    {

       static void Main(string[] args)

        {

            int A = -100, B = 100;

            int[] intervals = new int[Math.Abs(B) + Math.Abs(A) - 1];

            double[] pred = new double[5];//left

            double[] pred1 = new double[5];//right

            int k = 0;

            for (double i = A; i < B; i++)

            {

                if (f(i) * f(i + 1) < 0)

                {

                    pred[k] = i;

                    pred1[k] = i + 1;

                    k++;

                }

            }

            double c = 0;

            double a, b;

            double eps = 0.00001;

           for (int i = 0; i < 5; i++)