Теоретические основы разработки вычислительных систем

Тема 1.1

Численные методы решения инженерных задач

Точность и устойчивость, нелинейные уравнения, СЛАУ, интерполяция и аппроксимация, интегрирование, задача Коши.

Точность вычислений и устойчивость метода

Источники погрешности численного решения:

• неустранимая — погрешность исходных данных и самой математической модели;
• погрешность метода — от замены точной задачи приближённой (например, отбрасывание остатка ряда, конечный шаг сетки h);
• вычислительная (округления) — из-за конечной разрядности представления чисел в ЭВМ.

Методы решения нелинейного уравнения f(x) = 0

Этап 1 — отделение корня: находят отрезок [a, b], где f(a)·f(b) < 0 и корень один. Этап 2 — уточнение одним из методов:

• Половинного деления (бисекции) — делим отрезок пополам, оставляем половину со сменой знака. Сходится всегда, но медленно: за шаг интервал сужается вдвое.
• Хорд — новое приближение в точке пересечения хорды, соединяющей (a, f(a)) и (b, f(b)), с осью x.
• Ньютона (касательных): x_k+1 = x_k − f(x_k)/f′(x_k) — пересечение касательной с осью. Квадратичная сходимость вблизи корня, но нужна производная и хорошее начальное приближение.
• Простой итерации — уравнение приводят к виду x = φ(x) и итерируют x_k+1 = φ(x_k).

Сжимающее отображение и сходимость простой итерации

Теорема о сходимости: если φ — сжимающее отображение на отрезке и отображает отрезок в себя, то уравнение x = φ(x) имеет единственную неподвижную точку, и метод простой итерации сходится к ней из любого начального приближения. Практический признак: |φ′(x)| ≤ q < 1 в окрестности корня. Чем меньше q, тем быстрее сходимость; при |φ′| > 1 итерации расходятся. Оценка ошибки: |x_k − x*| ≤ q^k·|x₀ − x*| — геометрическая прогрессия со знаменателем q.

Прямые и итерационные методы решения СЛАУ

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

• Метод Гаусса — прямой ход (приведение к треугольному виду исключением неизвестных) и обратный ход (последовательное вычисление x_n, …, x₁). Трудоёмкость O(n³). Выбор главного элемента снижает влияние округлений.
• LU-разложение — A = LU, решение двух треугольных систем; выгодно при многих правых частях.
• Метод прогонки — вариант Гаусса для трёхдиагональных систем (возникают в разностных схемах), O(n) операций.

Итерационные строят последовательность приближений x^(k) → x*:

• Метод Якоби (простой итерации) — каждая компонента нового приближения считается по всем компонентам старого.
• Метод Гаусса–Зейделя — при вычислении i-й компоненты сразу используются уже уточнённые первые i−1 компонент; обычно сходится быстрее.

Достаточное условие сходимости — диагональное преобладание: |a_ii| > Σ_j≠i |a_ij|. Итерационные методы выгодны для больших разреженных систем.

Системы нелинейных уравнений

• Метод простой итерации: x_k+1 = Φ(x_k); сходится, если норма матрицы Якоби Φ меньше 1 (многомерное сжимающее отображение).
• Метод Ньютона: на каждом шаге решается СЛАУ J(x_k)·Δx = −F(x_k), где J — матрица Якоби; затем x_k+1 = x_k + Δx. Быстрый, но требует вычисления и обращения якобиана на каждом шаге.

Интерполяция табличной функции

• Полином Лагранжа: P(x) = Σ y_i·l_i(x), где базисные полиномы l_i(x) = Π_j≠i (x−x_j)/(x_i−x_j) равны 1 в «своём» узле и 0 в остальных. Недостаток: при добавлении узла пересчитывается целиком.
• Полином Ньютона с разделёнными разностями (произвольные узлы): P(x) = f(x₀) + f(x₀,x₁)(x−x₀) + f(x₀,x₁,x₂)(x−x₀)(x−x₁) + …, где разделённые разности строятся рекуррентно. Добавление узла — лишь новое слагаемое.
• Полином Ньютона с конечными разностями (равноотстоящие узлы, шаг h): используются конечные разности Δy_i = y_i+1 − y_i, Δ²y и т.д.; первая формула Ньютона — интерполяция в начале таблицы, вторая — в конце.

Сплайн-интерполяция. Вместо одного полинома высокой степени промежуток разбивают на части и на каждой строят полином малой степени, сшивая куски гладко. Кубический сплайн — на каждом отрезке полином 3-й степени; в узлах непрерывны сама функция, первая и вторая производные. Это стандартный ответ на эффект Рунге: гладкая кривая без раскачки краёв. Именно так работают лекала чертёжника и кривые в CAD.

Аппроксимация. Метод наименьших квадратов

МНК: параметры функции φ(x, a₀…a_m) выбирают из минимума суммы квадратов отклонений

Условия минимума ∂S/∂a_k = 0 дают систему нормальных уравнений — линейную СЛАУ относительно коэффициентов. Для прямой φ = a + bx получается система 2×2:

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

Интеграл заменяют квадратурной суммой по значениям функции в узлах на сетке с шагом h:

• Прямоугольников (левых/правых/средних) — точность O(h) для левых/правых, O(h²) для средних;
• Трапеций — площадь трапеций между узлами, точность O(h²);
• Симпсона (парабол) — участок из пары шагов заменяется параболой, точность O(h⁴), число шагов чётное.

Практическая оценка точности — правило Рунге: считают с шагами h и h/2 и сравнивают результаты.

Другие квадратурные формулы (семейство Ньютона–Котеса и не только):

• Правило 3/8 — кубическая парабола по трём шагам: (3h/8)·(f₀ + 3f₁ + 3f₂ + f₃); тот же порядок O(h⁴), что у Симпсона, применяется, когда число шагов кратно трём.
• Квадратуры Гаусса — узлы не равноотстоящие, а выбираются оптимально (корни полиномов Лежандра): n узлов дают точность для полиномов степени 2n−1 — вдвое «умнее» Ньютона–Котеса.

Метод Монте-Карло

Метод статистических испытаний (Монте-Карло) — вычисление интеграла случайными точками: бросаем N точек равномерно в прямоугольник, накрывающий график; доля точек, попавших под кривую, умноженная на площадь прямоугольника, оценивает интеграл. Точность растёт как 1/√N — медленно (для лишнего знака нужно в 100 раз больше точек), зато скорость не зависит от размерности: для 100-мерного интеграла (частая ситуация в статистике и машинном обучении) сеточные методы бессильны, а Монте-Карло работает так же.

Дифференцирование — заменой производной разностными отношениями: правая/левая разность (y_i+1−y_i)/h — O(h), центральная (y_i+1−y_i−1)/2h — O(h²), вторая производная (y_i+1−2y_i+y_i−1)/h² — O(h²). Операция некорректна к шуму: при уменьшении h ошибки данных усиливаются.

Задача Коши. Методы Эйлера и Рунге–Кутта

• Метод Эйлера: y_i+1 = y_i + h·f(x_i, y_i) — движение по касательной. Первый порядок точности O(h), ошибка быстро накапливается.
• Модифицированный Эйлер (Эйлера–Коши) — с пересчётом по среднему наклону, O(h²).
• Рунге–Кутта 4-го порядка: наклон усредняется по четырём пробным вычислениям f внутри шага. Точность O(h⁴) — стандарт де-факто:

Классификация методов для ОДУ, которую полезно назвать:

• одношаговые (Эйлер, Рунге–Кутта) — шаг только из текущей точки; легко стартуют и меняют шаг;
• многошаговые (Адамса) — используют несколько предыдущих точек: та же точность при меньшем числе вычислений f, но нужен «разгон» одношаговым методом;
• явные / неявные — в неявных y_i+1 входит в обе части и находится решением уравнения; они устойчивее и незаменимы для жёстких систем, где явные методы требуют неприемлемо малого шага.

Тема 1.2

Математическое моделирование

Модели и их свойства, аналогии подсистем, способы формирования моделей, краевые задачи: МКР и МКЭ.

Основные понятия

Назначение моделей: анализ и прогноз поведения объекта, проектирование и оптимизация, управление, обучение.

Классификация ММ

Свойства моделей и способы получения

• Точность — степень совпадения расчётных значений выходных параметров с истинными.
• Адекватность — способность отражать заданные свойства объекта с погрешностью не выше заданной. Область адекватности — область в пространстве внешних параметров, где погрешность модели остаётся в допустимых пределах.
• Экономичность — затраты вычислительных ресурсов (память, время) на реализацию модели.

Способы получения моделей:

• аналитический (теоретический) — из фундаментальных законов (сохранения массы, энергии, импульса, законов Кирхгофа, Ньютона): широкая область адекватности, но требует знания физики процессов;
• экспериментальный (формальный) — обработкой опытных данных (регрессия, МНК, планирование эксперимента): модель «чёрного ящика», работает только в области эксперимента;
• экспериментально-аналитический — структура из теории, коэффициенты из эксперимента (модель «серого ящика»).

Аналогии между подсистемами. Топологические и компонентные уравнения

Однородные физические подсистемы описываются одинаковыми по форме уравнениями через пары переменных: фазовую переменную типа потока и типа потенциала.

• Компонентные уравнения описывают отдельные элементы (связь тока и напряжения резистора, силы и скорости демпфера).
• Топологические уравнения описывают соединение элементов и следуют из структуры системы — аналоги законов Кирхгофа: сумма потоков в узле равна нулю, сумма потенциалов по контуру равна нулю.

Благодаря аналогиям любую однородную подсистему можно представить эквивалентной схемой из R-, C-, L-элементов и источников, а моделировать единым программным аппаратом.

Способы формирования ММ систем: обобщённый метод — в систему включаются все компонентные и топологические уравнения (переменные — все токи и напряжения ветвей); узловой метод — неизвестные только узловые потенциалы, уравнения — балансы потоков в узлах (размерность меньше, применяется в СAПР схемотехники).

Методы решения краевых задач

Краевая задача — уравнение (обычно в частных производных) плюс условия на границах области (и начальные условия для нестационарных задач).

Метод конечных разностей (МКР)

• Область покрывается сеткой; производные заменяются разностными отношениями; УрЧП превращается в систему алгебраических уравнений относительно значений в узлах.
• Погрешность аппроксимации — невязка от замены производных разностями, оценивается разложением в ряд Тейлора: O(h), O(h²)…
• Явная схема: значение на новом временном слое выражается непосредственно через известные значения старого слоя. Проста, но условно устойчива — шаг по времени ограничен (например, для уравнения теплопроводности Δt ≤ h²/2a).
• Неявная схема: в уравнение входят несколько неизвестных нового слоя — на каждом шаге решается СЛАУ (для одномерной задачи — прогонкой). Безусловно устойчива, шаг ограничен только точностью.
• Устойчивость разностной схемы — ошибки, внесённые на одном слое, не нарастают при переходе к следующим. Сходимость = аппроксимация + устойчивость.

Метод конечных элементов (МКЭ)

• Область разбивается на конечные элементы произвольной формы (треугольники, тетраэдры); решение внутри элемента приближается простыми базисными функциями (обычно полиномами).
• Коэффициенты находятся из минимизации функционала (вариационная постановка) или метода взвешенных невязок (Галёркина); собирается глобальная СЛАУ с разреженной матрицей.
• Преимущества перед МКР: естественно описывает сложную геометрию и граничные условия, легко сгущает сетку локально.

Метод прямых (сведение к ОДУ) и метод характеристик

Метод прямых: производные лишь по части переменных заменяются разностями — УрЧП сводится к системе ОДУ, которую решают методами типа Рунге–Кутта.

Метод характеристик — специальный метод для гиперболических УрЧП (волновое уравнение, перенос вещества потоком, нестационарные течения газа). У таких уравнений есть характеристики — выделенные кривые в плоскости (x, t), вдоль которых возмущения распространяются с конечной скоростью, а само УрЧП вырождается в обыкновенное дифференциальное уравнение (соотношение совместности). Алгоритм: из точек с известными данными выпускаются характеристики; в точке их пересечения интегрированием ОДУ вдоль каждой кривой находится решение — сетка строится «сама», следуя физике переноса.

Сравнение: МКР универсален для всех типов уравнений (параболических, эллиптических, гиперболических), метод характеристик точнее отслеживает фронты и разрывы, но применим только к гиперболическим задачам и сложен в многомерье.

Тема 1.3

Оптимизация

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

Постановка задачи и классификация

Критерии оптимальности:

• частный — один главный показатель, остальные переводятся в ограничения;
• аддитивный — взвешенная сумма частных критериев F = Σ w_if_i;
• мультипликативный — произведение F = Π f_i^w_i;
• максиминный — максимизация худшего из частных критериев: max min_i f_i (гарантированный результат).

Ограничения: равенства g(x) = 0, неравенства h(x) ≤ 0, прямые (a ≤ x_i ≤ b). Классификация задач: безусловная / условная; одномерная / многомерная; линейное программирование (критерий и ограничения линейны), нелинейное, целочисленное; задачи оптимального управления (искомая величина — функция времени).

Характеристика численных методов: методы спуска строят последовательность точек с убыванием критерия; конечношаговые методы достигают решения за конечное число шагов (симплекс-метод ЛП), бесконечношаговые — лишь в пределе. Порядок метода — старший порядок используемых производных (нулевой, первый, второй). Критерии окончания: |x_k+1 − x_k| < ε, |F_k+1 − F_k| < ε, ‖∇F‖ < ε.

Одномерная оптимизация

Условия оптимальности: необходимое — F′(x*) = 0; достаточное — F″(x*) > 0 (минимум). Численные методы сужают интервал неопределённости, где лежит минимум унимодальной функции:

• половинного деления — две пробные точки около середины, отбрасывание части интервала;
• «золотого» сечения — пробные точки делят интервал в отношении золотого сечения (τ ≈ 0,618), одна из точек переиспользуется на следующем шаге: одно вычисление функции за итерацию, сжатие в 0,618 раза;
• Фибоначчи — точки по числам Фибоначчи; при заданном числе вычислений даёт минимальный интервал (оптимальный пассивно-последовательный план).

Метод Ньютона для оптимизации — это метод касательных, применённый к уравнению F′(x) = 0:

Сходится за считанные шаги вблизи минимума, но требует унимодальности не спасает: при F″ < 0 шагнёт к максимуму. Методы интервалов (дихотомия, золотое сечение, Фибоначчи) медленнее, зато не требуют производных и гарантированно работают на любой унимодальной функции.

Многомерная оптимизация

Условия: необходимое — ∇F(x*) = 0; достаточное — матрица Гессе положительно определена (минимум).

• Методы нулевого порядка (только значения F): покоординатный спуск (Гаусса–Зейделя) — поочерёдная одномерная минимизация по каждой координате; метод Пауэлла — покоординатный спуск с построением сопряжённых направлений; симплексный метод (Нелдера–Мида) — деформируемый многогранник: отражение, растяжение, сжатие худшей вершины.
• Методы первого порядка: градиентный — шаг против градиента x_k+1 = x_k − λ∇F; наискорейшего спуска — λ на каждом шаге из одномерной минимизации вдоль антиградиента (траектория из взаимно перпендикулярных шагов); сопряжённых градиентов — направления корректируются с учётом предыдущих, квадратичную функцию n переменных минимизирует за n шагов.
• Метод «оврагов» — для функций с вытянутыми «оврагами», где градиентные методы «пилят» поперёк оврага: из двух близких точек спускаются на дно, затем делают большой шаг вдоль дна оврага.

Методы второго порядка. Метод Ньютона: шаг x_k+1 = x_k − H⁻¹∇F использует матрицу Гессе H (вторые производные) — учитывает кривизну и на квадратичной функции попадает в минимум за один шаг из любой точки. Дорог: n² вторых производных и обращение матрицы на каждом шаге. Квазиньютоновские методы (ДФП — Дэвидона–Флетчера–Пауэлла, БФГШ) — компромисс: приближение H⁻¹ накапливается по разностям градиентов соседних шагов, вторые производные не вычисляются вовсе.

Нелинейное программирование

Ограничения-равенства — метод множителей Лагранжа: строится функция L(x, λ) = F(x) + Σ λ_jg_j(x); необходимые условия — равенство нулю всех частных производных L по x и по λ. Множитель λ_j показывает чувствительность оптимума к ослаблению j-го ограничения.

Ограничения-неравенства — условия Куна–Таккера; решение соответствует седловой точке функции Лагранжа: по x — минимум, по λ ≥ 0 — максимум.

Численные методы НЛП:

• прямые — работают в допустимой области: прямой поиск с возвратом (нарушили ограничение — вернулись и уменьшили шаг), метод проекции градиента (шаг проецируется на границу допустимой области);
• методы штрафных функций — сводят условную задачу к последовательности безусловных: внешний штраф прибавляет к F большую «плату» за нарушение ограничений (приближение к решению снаружи), внутренний (барьерный) — барьер, растущий при подходе к границе изнутри (точки всегда допустимы); комбинированный метод — внутренний штраф для неравенств и внешний для равенств одновременно.

Вариационное исчисление

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

Простейшая задача: минимизировать J[y] при закреплённых концах y(a), y(b). Необходимое условие экстремума — уравнение Эйлера:

Для функционалов со старшими производными F(x, y, y′, y″, …) — уравнение Эйлера–Пуассона: F_y − d/dx F_y′ + d²/dx² F_y″ − … = 0. Частные случаи интегрируемости: если F не зависит от y, то F_y′ = C; если F не зависит от x — первый интеграл F − y′F_y′ = C.

Численные методы: уравнение Эйлера — краевая задача для ОДУ, решается методом пристрелки (подбор недостающего начального условия так, чтобы попасть в правое краевое) или прогонкой (для линейных задач). Прямые методы минимизируют сам функционал: метод Ритца — решение ищется как комбинация базисных функций y ≈ Σ a_iφ_i(x), задача сводится к минимизации функции коэффициентов; метод Канторовича — обобщение для функционалов от функций многих переменных (коэффициенты — функции); конечно-разностный метод Эйлера — интеграл заменяется суммой по сетке, функционал становится функцией узловых значений.

Условный экстремум: связи бывают голономные (φ(x, y₁, y₂, …) = 0 — без производных), неголономные (дифференциальные, с y′), изопериметрические (∫G dx = const — заданная «длина»). Необходимые условия строятся методом множителей Лагранжа: вспомогательный функционал с λ(x) (для изопериметрических λ — константа), для него записывается уравнение Эйлера.

Тема 1.4

Искусственный интеллект

Экспертные системы, представление знаний, нечёткие знания, модели поиска решений — по методичкам Коробовой и Обухова.

Подходы к искусственному интеллекту

Причина появления ИИ — потребность решать неформализованные задачи: без строгого алгоритма, с неполными и нечёткими данными, где решение строится на знаниях экспертов. Два исторических подхода:

• нисходящий (символьный) — моделирование рассуждений: представление знаний, логический вывод, экспертные системы;
• восходящий (нейросетевой) — моделирование биологических структур: нейронные сети, обучение на примерах.

Экспертные системы

• База знаний — формализованные знания предметной области: факты и правила.
• Механизм логического вывода — применяет правила к фактам, строит цепочку рассуждений.
• Модуль извлечения (приобретения) знаний — пополнение БЗ инженером знаний в диалоге с экспертом.
• Система объяснений — отвечает «почему получен такой вывод» перечнем сработавших правил (доверие пользователя, отладка БЗ).

Методология разработки ЭС (этапы): идентификация задачи → концептуализация (выделение понятий и связей) → формализация (выбор модели представления знаний) → выполнение (наполнение БЗ) → тестирование → опытная эксплуатация. Разработка ведётся быстрым прототипом с постепенным расширением: демонстрационный → исследовательский → действующий → промышленный → коммерческий уровень. Трудности: извлечение знаний у эксперта («узкое горло» инженерии знаний), верификация полноты и непротиворечивости БЗ, сопровождение. Перспективы: гибридные системы (правила + нейросети + нечёткая логика), самообучающиеся системы, интеграция с большими данными.

Инструментальные средства построения ЭС (способы построения): программирование «с нуля» на языках ИИ (Prolog — логический вывод «из коробки», Lisp — обработка символьных структур); оболочки ЭС — готовый механизм вывода и интерфейс, наполняется только база знаний (классика — EMYCIN, современные — CLIPS, Drools); гибридные инструментальные среды с несколькими моделями представления знаний. Выбор — компромисс: оболочка ускоряет разработку на порядок, но привязывает к своей модели знаний.

Способы представления знаний

• Продукционные правила — «ЕСЛИ условие ТО действие». Наглядны, модульны, легко пополняются; основной способ в ЭС.
• Фреймы — структура-«анкета» для стереотипной ситуации: имя, слоты со значениями, значениями по умолчанию, присоединёнными процедурами; фреймы образуют иерархии с наследованием.
• Семантические сети — ориентированный граф: вершины — понятия, дуги — отношения (is-a «является», part-of «часть», свойства). Вывод — поиск по сети.
• Логические модели — исчисление предикатов, вывод по правилам формальной логики (резолюция).
• Нейронные сети — знания в виде весов связей искусственных нейронов; нейрон вычисляет взвешенную сумму входов и пропускает через функцию активации; сети обучаются на примерах (обратное распространение ошибки), но не объясняют вывод.

Нечёткие знания

Операции (по Заде): дополнение μ_¬A = 1 − μ_A; пересечение μ_A∩B = min(μ_A, μ_B); объединение μ_A∪B = max(μ_A, μ_B).

Лингвистическая переменная — переменная, значениями которой являются слова («температура» = {низкая, средняя, высокая}); каждый терм — нечёткое множество с функцией принадлежности. Функции принадлежности строят по экспертным оценкам (прямое оценивание, парные сравнения) — обычно треугольные или трапециевидные.

Нечёткий вывод по обобщённому modus ponens: правила «ЕСЛИ x есть A ТО y есть B» с нечёткими посылками; этапы — фаззификация входов → вычисление степени истинности посылок (min/произведение) → агрегация заключений (max) → дефаззификация (например, центр тяжести). Так в ЭВМ представляют и обрабатывают нечёткие знания экспертов.

Модели поиска решений

• Прямая цепочка рассуждений (от данных к цели): просматриваются правила, посылки которых подтверждены фактами; их заключения добавляются в рабочую память — пока не будет получена цель. Хороша, когда данных мало, а гипотез много.
• Обратная цепочка (от цели к данным): выдвигается гипотеза-цель; ищутся правила, её выводящие; их посылки становятся подцелями — пока подцели не сведутся к известным фактам или вопросам пользователю. Хороша при небольшом числе возможных целей (диагностика).
• Поиск в пространстве состояний — граф «состояние → действия»: перебор в глубину/в ширину, эвристический поиск (A*); при больших пространствах — редукция задачи на подзадачи.