Количественная оценка информации. Формула Хартли, формула Шеннона.

21. Теория принятия решений
Фридман А.Я.

• 2 основных этапа многокритериальной оптимизации.

• Аксиома Парето и эффективные варианты. Определение множества Парето в дискретном и непрерывном случаях

• Количественная оценка эффективности решений: функция полезности

22. Технология программирования
Тоичкин Н.А.

• Рекурсивные алгоритмы. Примеры рекурсивных алгоритмов

• Анализ временной сложности (трудоемкости) алгоритмов

23. Численные методы/Вычислительная математика
Малыгина С.Н.

• Постановка задач аппроксимации функций одной переменной: Интерполирование алгебраическими многочленами.

В основе большинства численных методов математического анализа лежит подмена одной функции (известной, неизвестной или частично известной) другой функцией , близкой к и обладающей «хорошими» свойствами, позволяющими легко производить над нею те или иные аналитические или вычислительные операции. Такая подмена называется аппроксимацией или просто приближением функции функцией . Такую подмену можно сделать разными способами. Интерполирование Постановка задачи, пример возникновения задачи интерполирования   Интерполирование алгебраическими многочленами Пусть на отрезке заданы точки (будем называть их узлами интерполирования), в которых известны значения функции . Задача интерполирования алгебраическими многочленами состоит в том, чтобы построить многочлен степени , (1) значения которого в заданных точках совпадают со значениями функции в этих точках. Для любой непрерывной функции сформулированная задача имеет единственное решение. Действительно, для отыскания коэффициентов получаем систему линейных уравнений (2) Если среди нет совпадающих, то определитель системы (1.2) отличен от нуля, и следовательно система имеет единственное решение. Определение Многочлен , удовлетворяющий условию (3) называется интерполяционным многочленом для функции , построенным по узлам . Решение системы (1.2) можно записать различным образом. Наиболее употребительна запись интерполяционного многочлена в форме Лагранжа и в форме Ньютона. Интерполяционный многочлен Лагранжа имеет вид (4) Интерполяционная формула Ньютона позволяет выразить интерполяционный многочлен через значения в одном из узлов и через разделенные разности функции , построенные по узлам . Интерполяционным многочленом Ньютона называется многочлен , (5) где - разделенные разности. Интерполяционную формулу Ньютона удобнее применять в том случае, когда интерполируется одна и та же функция , но число узлов интерполирования увеличивается. Если узлы интерполяции фиксированы и интерполируется не одна, а несколько функций, то удобнее пользоваться формулой Лагранжа.

• Методы решения систем линейных алгебраических уравнений

План ответа: · Постановка задачи · Прямые методы (определение, примеры) · Итерационные методы (определение, понятие одношаговых и двухшаговых методов, условия окончания итераций, каноническая форма записи итерационных методов, понятие стационарных, нестационарных, явных и неявных методов, понятие матрицы перехода от n -ой итерации к (n +1)-ой, достаточное условие сходимости стационарных методов, необходимое и достаточное условие сходимости стационарных методов) Рассмотрим задачу численного решения системы вида (1) В матричном виде она записывается Ax = b,(1а) где - вектор свободных членов; - вектор неизвестных с вещественными координатами; - вещественная квадратная матрица коэффициентов системы размерности . Будем предполагать, что определитель матрицы A отличен от нуля. Тогда для каждого вектора b система (1) имеет единственное решение. Для решения таких систем можно использовать как прямые, так и итерационные методы. Прямые методы позволяют за конечное число действий получить точное решение системы уравнений, если входная информация задана точно и вычисления ведутся без округления (напр., методы Гаусса, Крамера и т.п.).   Итерационный метод позволяет найти приближенное решение системы путем построения последовательности приближений (итераций), начиная с некоторого начального приближения. Само приближенное решение является результатом вычислений, полученным после конечного числа итераций. Перейдем к общему описанию метода итераций для решения СЛАУ. Будем рассматривать систему (1) Для ее решения выбирается некоторое начальное приближение , и последовательно находятся приближенные решения (итерации) уравнения (5.1). Значение итерации выражается через известные предыдущие итерации . В дальнейшем верхний индекс будет указывать номер итерации, т.е. , где - n -ая итерация i –той компоненты вектора x. Определение 1 Если при вычислении используется только одна предыдущая итерация , то итерационный метод называют одношаговым (или двухслойным) методом; если же выражается через две итерации и , то метод называют двухшаговым (или трехслойным).   Окончание итераций определяется либо заданием максимального числа итераций , либо условием , (2) где e > 0 – заданное число. Определение 2. Канонической формой одношагового итерационного метода решения системы вида (5.1) называется его запись в виде (3) Здесь - матрица, задающая тот или иной итерационный метод, - итерационный параметр, - вектор, полученный на n – ой итерации. Предполагается, что задано начальное приближение и существует . Определение 3. Итерационный метод (3) называется явным, если , неявным, если , где E – единичная матрица. Определение 4. Итерационный метод (3) называется стационарным, если и , т.е. не зависят от номера итерации, и нестационарным – в противоположном случае. Определение 5. Матрица называется матрицей перехода от n -ой итерации к (n +1)-ой. Теорема 1. (Необходимое и достаточное условие сходимости) Итерационный метод сходится при любом начальном приближении, тогда и только тогда, когда все собственные значения матрицы перехода S по модулю меньше единицы. Теорема 2. (Достаточное условие сходимости) Итерационный метод сходится при любом начальном приближении, если норма матрицы перехода S меньше единицы.