Опис методу найменших квадратів для параметрів рівняння. Метод найменших квадратів

100 рбонус за перше замовлення

Оберіть тип роботи Дипломна робота Курсова робота Реферат Магістерська дисертація Звіт з практики Стаття Доповідь Рецензія Контрольна робота Монографія Рішення задач Бізнес-план Відповіді на запитання Творча робота Есе Чертеж Твори Переклад Презентації Набір тексту Інше Підвищення унікальності тексту

Дізнатись ціну

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

Напр., за наявними даними ( xi,yi) (i = 1, 2, ..., n) будується така крива y = a + bx, на якій досягається мінімум суми квадратів відхилень

тобто мінімізується функція, яка залежить від двох параметрів: a- відрізок на осі ординат та b- Нахил прямий.

Рівняння, що дають необхідні умови для мінімізації функції S(a,b), називаються нормальними рівняннями.Як апроксимуючі функції застосовуються не тільки лінійна (вирівнювання по прямій лінії), але і квадратична, параболічна, експоненційна та ін. Приклад вирівнювання динамічного ряду по прямій див. на рис. M.2 де сума квадратів відстаней ( y 1 – ȳ 1)2 + (y 2 – ȳ 2)2 .... - найменша, і пряма, що вийшла, найкращим чином відображає тенденцію динамічного ряду спостережень за деяким показником у часі.

Для незміщеності МНК-оцінок необхідно і достатньо виконання найважливішої умови регресійного аналізу: умовне за факторами математичне очікування випадкової помилки має дорівнювати нулю. Ця умова, зокрема, виконано, якщо: 1. математичне очікування випадкових помилок дорівнює нулю, і 2. фактори та випадкові помилки – незалежні випадкові величини. Першу умову можна вважати виконаною завжди для моделей з константою, оскільки константа бере на себе ненульове математичне очікування помилок. Друга умова - умова екзогенності факторів - важлива. Якщо це властивість не виконано, можна вважати, що будь-які оцінки будуть вкрай незадовільними: де вони навіть заможними (тобто навіть дуже великий обсяг даних Демшевського не дозволяє отримати якісні оцінки у разі).

Найбільш поширеним у практиці статистичного оцінювання параметрів рівнянь регресії є метод найменших квадратів. Цей метод заснований на низці передумов щодо природи даних та результатів побудови моделі. Основні з них - це чіткий поділ вихідних змінних на залежні та незалежні, некорелюваність факторів, що входять до рівнянь, лінійність зв'язку, відсутність автокореляції залишків, рівність їх математичних очікувань нулю та постійна дисперсія.

Однією з основних гіпотез МНК є припущення рівності дисперсій відхилень еi, тобто. їх розкид навколо середнього (нульового) значення ряду має бути величиною стабільною. Ця властивість називається гомоскедастичністю. На практиці дисперсії відхилень досить часто неоднакові, тобто спостерігається гетероскедастичність. Це може бути наслідком різних причин. Наприклад, можливі помилки у вихідних даних. Випадкові неточності у вихідній інформації, такі як помилки в порядку чисел, можуть вплинути на результати. Часто більший розкид відхилень є, спостерігається при великих значеннях залежної змінної (змінних). Якщо даних міститься значна помилка, то, природно, великим буде і відхилення модельного значення, розрахованого за помилковими даними. Для того, щоб позбавитися цієї помилки нам потрібно зменшити внесок цих даних у результати розрахунків, задати для них меншу вагу, ніж для всіх інших. Ця ідея реалізована у виваженому МНК.

приклад.

Експериментальні дані про значення змінних хі унаведено у таблиці.

В результаті їх вирівнювання отримано функцію

Використовуючи метод найменших квадратів, апроксимувати ці дані лінійною залежністю y=ax+b(Знайти параметри аі b). З'ясувати, яка з двох ліній краще (у сенсі способу менших квадратів) вирівнює експериментальні дані. Зробити креслення.

Суть методу найменших квадратів (МНК).

Завдання полягає у знаходженні коефіцієнтів лінійної залежності, при яких функція двох змінних аі b набуває найменшого значення. Тобто, за даними аі bсума квадратів відхилень експериментальних даних від знайденої прямої буде найменшою. У цьому суть методу найменших квадратів.

Таким чином, рішення прикладу зводиться до знаходження екстремуму функції двох змінних.

Висновок формул знаходження коефіцієнтів.

Складається та вирішується система із двох рівнянь із двома невідомими. Знаходимо приватні похідні функції змінних аі b, Прирівнюємо ці похідні до нуля.

Вирішуємо отриману систему рівнянь будь-яким методом (наприклад методом підстановкиабо ) і отримуємо формули для знаходження коефіцієнтів методом найменших квадратів (МНК).

За даними аі bфункція набуває найменшого значення. Доказ цього факту наведено.

Ось і весь спосіб найменших квадратів. Формула для знаходження параметра aмістить суми , , , та параметр n- Кількість експериментальних даних. Значення цих сум рекомендуємо обчислювати окремо. Коефіцієнт bзнаходиться після обчислення a.

Настав час згадати про вихідний приклад.

Рішення.

У нашому прикладі n=5. Заповнюємо таблицю для зручності обчислення сум, що входять до формул шуканих коефіцієнтів.

Значення у четвертому рядку таблиці отримані множенням значень 2-го рядка на значення 3-го рядка для кожного номера i.

Значення у п'ятому рядку таблиці отримані зведенням у квадрат значень другого рядка для кожного номера i.

Значення останнього стовпця таблиці – це суми значень рядків.

Використовуємо формули методу найменших квадратів для знаходження коефіцієнтів аі b. Підставляємо у них відповідні значення з останнього стовпця таблиці:

Отже, y = 0.165x+2.184- пряма апроксимуюча.

Залишилося з'ясувати, яка з ліній y = 0.165x+2.184або краще апроксимує вихідні дані, тобто провести оцінку шляхом найменших квадратів.

Оцінка похибки способу менших квадратів.

Для цього потрібно обчислити суми квадратів відхилень вихідних даних від цих ліній і менше значення відповідає лінії, яка краще в сенсі методу найменших квадратів апроксимує вихідні дані.

Оскільки , то пряма y = 0.165x+2.184краще наближає вихідні дані.

Графічна ілюстрація методу найменших квадратів (МНК).

На графіках все чудово видно. Червона лінія – це знайдена пряма y = 0.165x+2.184, синя лінія – це , Рожеві точки - це вихідні дані.

Навіщо це потрібно, до чого всі ці апроксимації?

Я особисто використовую для вирішення завдань згладжування даних, задач інтерполяції та екстраполяції (у вихідному прикладі могли б попросити знайти значення спостережуваної величини yпри x=3або при x=6методом МНК). Але докладніше поговоримо про це пізніше в іншому розділі сайту.

Доказ.

Щоб при знайдених аі bфункція приймала найменше значення, необхідно, щоб у цій точці матриця квадратичної форми диференціала другого порядку для функції була позитивно визначеною. Покажемо це.

Метод найменших квадратів

Метод найменших квадратів ( МНК, OLS, Ordinary Least Squares) - один із базових методів регресійного аналізу для оцінки невідомих параметрів регресійних моделей за вибірковими даними. Метод ґрунтується на мінімізації суми квадратів залишків регресії.

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

Сутність МНК

Нехай задана деяка (параметрична) модель імовірнісної (регресійної) залежності між (з'ясованою) змінною yі безліччю факторів (що пояснюють змінних) x

де - вектор невідомих параметрів моделі

Нехай також є вибіркові спостереження значень вказаних змінних. Нехай – номер спостереження (). Тоді - значення змінних у спостереженні. Тоді при заданих значеннях параметрів b можна розрахувати теоретичні (модельні) значення змінної, що пояснюється y:

Розмір залишків залежить від значень параметрів b.

Сутність МНК (звичайного, класичного) у тому, щоб знайти такі параметри b, у яких сума квадратів залишків (англ. Residual Sum of Squares) буде мінімальною:

У випадку вирішення цього завдання може здійснюватися чисельними методами оптимізації (мінімізації). У цьому випадку говорять про нелінійному МНК(NLS або NLLS – англ. Non-Linear Least Squares). У багатьох випадках можна одержати аналітичне рішення. Для вирішення задачі мінімізації необхідно знайти стаціонарні точки функції, продиференціювавши її за невідомими параметрами b, прирівнявши похідні до нуля і вирішивши отриману систему рівнянь:

Якщо випадкові помилки моделі мають нормальний розподіл , мають однакову дисперсію і некорельовані між собою, МНК оцінки параметрів збігаються з оцінками методу максимальної правдоподібності (ММП).

МНК у разі лінійної моделі

Нехай регресійна залежність є лінійною:

Нехай y- Вектор-стовпець спостережень пояснюваної змінної, а - матриця спостережень факторів (рядки матриці - вектори значень факторів у даному спостереженні, по стовпцях - вектор значень даного фактора у всіх спостереженнях). Матричне уявлення лінійної моделі має вигляд:

Тоді вектор оцінок змінної, що пояснюється, і вектор залишків регресії дорівнюватимуть

відповідно сума квадратів залишків регресії дорівнюватиме

Диференціюючи цю функцію за вектором параметрів та прирівнявши похідні до нуля, отримаємо систему рівнянь (у матричній формі):

Вирішення цієї системи рівнянь і дає загальну формулу МНК-оцінок для лінійної моделі:

Для аналітичних цілей виявляється корисним останнє уявлення цієї формули. Якщо у регресійній моделі дані центровані, то цьому поданні перша матриця має сенс вибіркової ковариационной матриці чинників, а друга - вектор ковариаций чинників із залежною змінною. Якщо дані ще й нормованіна СКО (тобто зрештою стандартизовано), то перша матриця має сенс вибіркової кореляційної матриці факторів, другий вектор - вектора вибіркових кореляцій факторів із залежною змінною.

Важлива властивість МНК-оцінок для моделей з константою- лінія побудованої регресії проходить через центр тяжкості вибіркових даних, тобто виконується рівність:

Зокрема, у крайньому випадку, коли єдиним регресором є константа, отримуємо, що МНК-оцінка єдиного параметра (власне константи) дорівнює середньому значенню змінної, що пояснюється. Тобто середнє арифметичне, відоме своїми добрими властивостями із законів великих чисел, також є МНК-оцінкою – задовольняє критерію мінімуму суми квадратів відхилень від неї.

Приклад: найпростіша (парна) регресія

У разі парної лінійної регресії формули розрахунку спрощуються (можна обійтися без матричної алгебри):

Властивості МНК-оцінок

Насамперед, зазначимо, що для лінійних моделей МНК-оцінки є лінійними оцінками, як це випливає з вищенаведеної формули. Для незміщеності МНК-оцінок необхідно і достатньо виконання найважливішої умови регресійного аналізу: умовне за факторами математичне очікування випадкової помилки має дорівнювати нулю. Ця умова, зокрема, виконана, якщо

1. математичне очікування випадкових помилок дорівнює нулю, та
2. фактори та випадкові помилки - незалежні випадкові величини.

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

Для того, щоб крім спроможності та незміщеності, оцінки (звичайного) МНК були ще й ефективними (найкращими в класі лінійних незміщених оцінок) необхідно виконання додаткових властивостей випадкової помилки:

Дані припущення можна сформулювати для коварійної матриці вектора випадкових помилок

Лінійна модель, що задовольняє такі умови, називається класичною. МНК-оцінки для класичної лінійної регресії є незміщеними, заможними та найбільш ефективними оцінками в класі всіх лінійних незміщених оцінок (в англомовній літературі іноді вживають абревіатуру BLUE (Best Linear Unbaised Estimator) - найкраща лінійна незміщена оцінка; у вітчизняній літературі найчастіше наводиться теорема Гауса – Маркова). Як неважко показати, коварійна матриця вектора оцінок коефіцієнтів дорівнюватиме:

Узагальнений МНК

Метод найменших квадратів припускає широке узагальнення. Замість мінімізації суми квадратів залишків можна мінімізувати деяку позитивно визначену квадратичну форму від вектора залишків де - деяка симетрична позитивно визначена вагова матриця. Звичайний МНК є окремим випадком даного підходу, коли вагова матриця пропорційна одиничній матриці. Як відомо з теорії симетричних матриць (або операторів) для таких матриць існує розкладання. Отже, зазначений функціонал можна уявити наступним чином , тобто цей функціонал можна як суму квадратів деяких перетворених «залишків». Отже, можна назвати клас методів найменших квадратів - LS-методи (Least Squares).

Доведено (теорема Айткена), що для узагальненої лінійної регресійної моделі (у якій на коварійну матрицю випадкових помилок не накладається жодних обмежень) найефективнішими (у класі лінійних незміщених оцінок) є оцінки т.з. узагальненого МНК (ОМНК, GLS - Generalized Least Squares)- LS-метода з ваговою матрицею, що дорівнює зворотній коварійній матриці випадкових помилок: .

Можна показати, що формула ОМНК оцінок параметрів лінійної моделі має вигляд

Коваріаційна матриця цих оцінок відповідно дорівнюватиме

Фактично сутність ОМНК полягає у певному (лінійному) перетворенні (P) вихідних даних та застосуванні звичайного МНК до перетворених даних. Ціль цього перетворення - для перетворених даних випадкові помилки вже задовольняють класичним припущенням.

Зважений МНК

У випадку діагональної вагової матриці (а значить і матриці коварійної випадкових помилок) маємо так званий зважений МНК (WLS - Weighted Least Squares). У разі мінімізується зважена сума квадратів залишків моделі, тобто кожне спостереження отримує «вага», зворотно пропорційний дисперсії випадкової помилки у цьому спостереженні: . Фактично дані перетворюються зважуванням спостережень (розподілом на величину, пропорційну передбачуваному стандартному відхилення випадкових помилок), а зваженим даним застосовується звичайний МНК.

Деякі окремі випадки застосування МНК на практиці

Апроксимація лінійної залежності

Розглянемо випадок, коли в результаті вивчення залежності деякої скалярної величини від деякої скалярної величини (Це може бути, наприклад, залежність напруги від сили струму : де - постійна величина, опір провідника) було проведено вимірювань цих величин, в результаті яких були отримані значення і відповідні їм значення. Дані вимірювань мають бути записані у таблиці.

Таблиця. Результати вимірів.

Питання звучить так: яке значення коефіцієнта можна підібрати, щоб якнайкраще описати залежність? Згідно з МНК це значення має бути таким, щоб сума квадратів відхилень величин від величин

була мінімальною

Сума квадратів відхилень має один екстремум – мінімум, що дозволяє нам використовувати цю формулу. Знайдемо з цієї формули значення коефіцієнта. І тому перетворимо її ліву частину так:

Остання формула дозволяє знайти значення коефіцієнта , що й потрібно завдання.

Історія

На початок ХІХ ст. вчені у відсутності певних правил на вирішення системи рівнянь , у якій число невідомих менше, ніж число рівнянь; до цього часу використовувалися приватні прийоми, що залежали від виду рівнянь і від дотепності обчислювачів, і тому різні обчислювачі, виходячи з тих самих даних спостережень, приходили до різних висновків. Гаусс (1795) належить перше застосування методу, а Лежандр (1805) незалежно відкрив і опублікував його під сучасною назвою (фр. Méthode des moindres quarrés ). Лаплас пов'язав метод з теорією ймовірностей, а американський математик Едрейн (1808) розглянув його теоретико-імовірнісні додатки. Метод поширений і вдосконалений подальшими дослідженнями Енке, Бесселя, Ганзена та інших.

Альтернативне використання МНК

Ідея методу найменших квадратів може бути використана також в інших випадках, які не пов'язані безпосередньо з регресійним аналізом. Справа в тому, що сума квадратів є одним із найпоширеніших заходів близькості для векторів (евклідова метрика в кінцевомірних просторах).

Одне із застосувань - «вирішення» систем лінійних рівнянь, у яких число рівнянь більше числа змінних

де матриця не квадратна, а прямокутна розміру.

Така система рівнянь, у випадку немає рішення (якщо ранг насправді більше числа змінних). Тому цю систему можна «вирішити» тільки в сенсі вибору такого вектора, щоб мінімізувати «відстань» між векторами та . І тому можна застосувати критерій мінімізації суми квадратів різниць лівої та правої частин рівнянь системи, тобто . Неважко показати, що вирішення цього завдання мінімізації призводить до вирішення наступної системи рівнянь

Він має безліч застосувань, оскільки дозволяє здійснювати наближене уявлення заданої функції іншими більш простими. МНК може виявитися надзвичайно корисним при обробці спостережень і його активно використовують для оцінки одних величин за результатами вимірювань інших, що містять випадкові помилки. З цієї статті ви дізнаєтеся, як реалізувати обчислення методом найменших квадратів в Excel.

Постановка задачі на конкретному прикладі

Припустимо, є два показники X і Y. Причому Y залежить від X. Так як МНК цікавить нас з погляду регресійного аналізу (в Excel його методи реалізуються за допомогою вбудованих функцій), то відразу ж перейти до розгляду конкретної задачі.

Отже, нехай X — торгова площа продовольчого магазину, яка вимірюється у квадратних метрах, а Y — річний товарообіг, який визначається мільйонами рублів.

Потрібно зробити прогноз, який товарообіг (Y) матиме магазин, якщо в нього та чи інша торгова площа. Очевидно, що функція Y = f(X) зростаюча, оскільки гіпермаркет продає більше товарів, ніж ларьок.

Декілька слів про коректність вихідних даних, що використовуються для передбачення

Припустимо, ми маємо таблицю, побудовану за даними для n магазинів.

Згідно з математичною статистикою, результати будуть більш-менш коректними, якщо досліджуються дані щодо хоча б 5-6 об'єктів. Крім того, не можна використовувати "аномальні" результати. Зокрема, невеликий елітний бутік може мати товарообіг у рази більший, ніж товарообіг великих торгових точок класу «масмаркет».

Суть методу

Дані таблиці можна зобразити на декартовій площині у вигляді точок M 1 (x 1 y 1), … M n (x n y n). Тепер розв'язання задачі зведеться до підбору апроксимуючої функції y = f(x), що має графік, що проходить якомога ближче до точок M1, M2,.. Mn.

Звичайно, можна використовувати багаточлен високого ступеня, але такий варіант не тільки важко реалізувати, але й просто некоректний, тому що не відображатиме основну тенденцію, яку і потрібно виявити. Найрозумнішим рішенням є пошук прямої у = ax + b, яка найкраще наближає експериментальні дані, a точніше, коефіцієнтів – a та b.

Оцінка точності

При будь-якій апроксимації особливої ​​важливості набуває оцінка її точності. Позначимо через e i різницю (відхилення) між функціональними та експериментальними значеннями для точки x i , тобто e i = y i - f (x i).

Очевидно, що для оцінки точності апроксимації можна використовувати суму відхилень, тобто при виборі прямої для наближеного уявлення залежності X від Y потрібно віддавати перевагу тій, у якої найменше значення суми e i у всіх точках. Однак, не все так просто, тому що поряд із позитивними відхиленнями практично будуть присутні і негативні.

Вирішити питання можна, використовуючи модулі відхилень або їх квадрати. Останній метод набув найбільш широкого поширення. Він використовується в багатьох областях, включаючи регресійний аналіз (в Excel його реалізація здійснюється за допомогою двох вбудованих функцій) і давно довів свою ефективність.

Метод найменших квадратів

В Excel, як відомо, існує вбудована функція автосуми, що дозволяє обчислити значення всіх значень, які розташовані у виділеному діапазоні. Таким чином, ніщо не завадить нам розрахувати значення виразу (e 1 2 + e 2 2 + e 3 2 + ... e n 2).

У математичному записі це має вигляд:

Оскільки спочатку було прийнято рішення про апроксимування за допомогою прямої, то маємо:

Таким чином, завдання знаходження прямої, яка найкраще описує конкретну залежність величин X та Y, зводиться до обчислення мінімуму функції двох змінних:

Для цього потрібно прирівняти до нуля приватні похідні за новими змінними a і b, і вирішити примітивну систему, що складається з двох рівнянь з двома невідомими видами:

Після нехитрих перетворень, включаючи поділ на 2 та маніпуляції із сумами, отримаємо:

Вирішуючи її, наприклад, методом Крамера, отримуємо стаціонарну точку з деякими коефіцієнтами a* та b*. Це і є мінімум, тобто для передбачення, який товарообіг буде у магазину при певній площі, підійде пряма y = a * x + b * , Що являє собою регресійну модель для прикладу, про який йдеться. Звичайно, вона не дозволить знайти точний результат, але допоможе одержати уявлення про те, чи окупиться покупка в кредит магазину конкретної площі.

Як реалізувати метод найменших квадратів в Excel

У "Ексель" є функція для розрахунку значення МНК. Вона має такий вигляд: «ТЕНДЕНЦІЯ» (відоме значення Y; відоме значення X; нові значення X; конст.). Застосуємо формулу розрахунку МНК Excel до нашої таблиці.

Для цього в комірку, в якій має бути відображено результат розрахунку за методом найменших квадратів в Excel, введемо знак = і виберемо функцію ТЕНДЕНЦІЯ. У вікні заповнимо відповідні поля, виділяючи:

• діапазон відомих значень для Y (у разі дані для товарообігу);
• діапазон x 1, … x n, тобто величини торгових площ;
• і відомі, і невідомі значення x, для якого потрібно з'ясувати розмір товарообігу (інформацію про їхнє розташування на робочому аркуші див. далі).

Крім того, у формулі є логічна змінна «Конст». Якщо ввести у відповідне їй поле 1, це означатиме, що слід здійснити обчислення, вважаючи, що b = 0.

Якщо потрібно дізнатися прогноз більш ніж одного значення x, то після введення формули слід натиснути не на «Введення», а потрібно набрати на клавіатурі комбінацію «Shift» + «Control» + «Enter» («Введення»).

Деякі особливості

Регресійний аналіз може бути доступним навіть чайникам. Формула Excel для передбачення значення масиву невідомих змінних – «ТЕНДЕНЦІЯ» – може використовуватися навіть тими, хто ніколи не чув про метод найменших квадратів. Достатньо просто знати деякі особливості її роботи. Зокрема:

• Якщо розташувати діапазон відомих значень змінної y в одному рядку або стовпці, то кожен рядок (стовпець) з відомими значеннями x сприйматиметься програмою як окрема змінна.
• Якщо у вікні «ТЕНДЕНЦІЯ» не вказаний діапазон з відомими x, то у разі використання функції Excel програма буде розглядати його як масив, що складається з цілих чисел, кількість яких відповідає діапазону із заданими значеннями змінної y.
• Щоб одержати на виході масив "передбачених" значень, вираз для обчислення тенденції потрібно вводити як формулу масиву.
• Якщо не вказано нових значень x, то функція «ТЕНДЕНЦІЯ» вважає їх рівним відомим. Якщо вони не задані, то як аргумент береться масив 1; 2; 3; 4;…, який пропорційний діапазону з вже заданими параметрами y.
• Діапазон, що містить нові значення x, повинен складатися з такої ж чи більшої кількості рядків або стовпців, як діапазон із заданими значеннями y. Іншими словами він має бути пропорційним незалежним змінним.
• У масиві з відомими значеннями x може бути кілька змінних. Однак якщо йдеться лише про одну, то потрібно, щоб діапазони із заданими значеннями x та y були пропорційні. У разі кількох змінних потрібно, щоб діапазон із заданими значеннями y вміщався в одному стовпчику або в одному рядку.

Функція «ПЕРЕДСКАЗ»

Реалізується за допомогою кількох функцій. Одна з них називається «Предказ». Вона аналогічна «ТЕНДЕНЦІЇ», тобто видає результат обчислень методом найменших квадратів. Однак лише для одного X, для якого невідомо значення Y.

Тепер ви знаєте формули в Excel для чайників, що дозволяють спрогнозувати величину майбутнього значення того чи іншого показника згідно з лінійним трендом.

• Tutorial

Вступ

Я математик-програміст. Найбільший стрибок у своїй кар'єрі я зробив, коли навчився говорити: "Я нічого не розумію!"Зараз мені не соромно сказати світилу науки, що читає лекцію, що я не розумію, про що воно, світило, мені говорить. І це дуже складно. Так, зізнатися у своєму незнанні складно та соромно. Кому сподобається визнаватись у тому, що він не знає азів чогось там. Через свою професію я повинен бути присутнім на великій кількості презентацій та лекцій, де, зізнаюся, в переважній більшості випадків мені хочеться спати, бо я нічого не розумію. А я не розумію тому, що величезна проблема поточної ситуації в науці криється в математиці. Вона припускає, що всі слухачі знайомі з усіма областями математики (що абсурдно). Зізнатися в тому, що ви не знаєте, що таке похідна (про те, що це трохи пізніше) - соромно.

Але я навчився говорити, що не знаю, що таке множення. Так, я не знаю, що таке подалгебра над алгеброю Лі. Так, я не знаю, навіщо потрібні у житті квадратні рівняння. До речі, якщо ви впевнені, що ви знаєте, то нам є над чим поговорити! Математика – це серія фокусів. Математики намагаються заплутати та залякати публіку; там, де немає збентеження, немає репутації, немає авторитету. Так, це престижно говорити якомога абстрактнішою мовою, що є по собі повна нісенітниця.

Чи знаєте ви, що таке похідна? Найімовірніше ви мені скажете про межу різницевого відношення. На першому курсі матуху СПбГУ Віктор Петрович Хавін мені визначивпохідну як коефіцієнт першого члена ряду Тейлора функції у точці (це була окрема гімнастика, щоб визначити ряд Тейлора без похідних). Я довго сміявся над таким визначенням, поки не зрозумів, про що воно. Похідна не що інше, як просто міра того, наскільки функція, яку ми диференціюємо, схожа на функцію y=x, y=x^2, y=x^3.

Я зараз маю честь читати лекції студентам, які боятьсяматематики. Якщо ви боїтеся математики – нам з вами по дорозі. Як тільки ви намагаєтеся прочитати якийсь текст, і вам здається, що він надмірно складний, то знайте, що він написано хронічно. Я стверджую, що немає жодної галузі математики, про яку не можна говорити «на пальцях», не втрачаючи при цьому точності.

Завдання найближчим часом: я доручив своїм студентам зрозуміти, що таке лінійно-квадратичний регулятор. Не посоромтеся, витратите три хвилини свого життя, сходіть на заслання. Якщо ви нічого не зрозуміли, то нам з вами по дорозі. Я (професійний математик-програміст) також нічого не зрозумів. І я запевняю, що в цьому можна розібратися «на пальцях». На даний момент я не знаю, що це таке, але я запевняю, що ми зможемо розібратися.

Отже, перша лекція, яку я збираюся прочитати своїм студентам після того, як вони з жахом вдадуться до мене зі словами, що лінійно-квадратичний регулятор - це страшна бяка, яку ніколи в житті не подужати, це методи найменших квадратів. Чи вмієте ви розв'язувати лінійні рівняння? Якщо ви читаєте цей текст, то, швидше за все, ні.

Отже, дано дві точки (x0, y0), (x1, y1), наприклад, (1,1) і (3,2), завдання знайти рівняння прямої, що проходить через ці дві точки:

ілюстрація

Ця пряма повинна мати рівняння наступного типу:

Тут альфа і бета нам невідомі, але відомі дві точки цієї прямої:

Можна записати це рівняння у матричному вигляді:

Тут слід створити ліричний відступ: що таке матриця? Матриця це не що інше, як двовимірний масив. Це спосіб зберігання даних, більше ніяких значень йому не варто надавати. Це залежить від нас, як саме інтерпретувати якусь матрицю. Періодично я її інтерпретуватиму як лінійне відображення, періодично як квадратичну форму, а ще іноді просто як набір векторів. Це все буде уточнено у контексті.

Давайте замінимо конкретні матриці на їхнє символьне уявлення:

Тоді (alpha, beta) може бути легко знайдено:

Більш конкретно для наших попередніх даних:

Що веде до наступного рівняння прямої, що проходить через точки (1,1) та (3,2):

Окей, тут зрозуміло. А давайте знайдемо рівняння прямої, що проходить через триточки: (x0, y0), (x1, y1) та (x2, y2):

Ой-ой-ой, але ж у нас три рівняння на дві невідомі! Стандартний математик скаже, що рішення немає. А що скаже програміст? А він спершу перепише попередню систему рівнянь у наступному вигляді:

У нашому випадку вектори i,j,b тривимірні, отже, (загалом) рішення цієї системи немає. Будь-який вектор (alpha i i beta i j) лежить у площині, натягнутій на вектори (i, j). Якщо b не належить цій площині, то рішення немає (рівності у рівнянні не досягти). Що робити? Давайте шукати компроміс. Давайте позначимо через e(alpha, beta)наскільки саме ми не досягли рівності:

І намагатимемося мінімізувати цю помилку:

Чому квадрат?

Ми шукаємо не просто мінімум норми, а мінімум квадрата норми. Чому? Сама точка мінімуму збігається, а квадрат дає гладку функцію (квадратичну функцію від агрументів (alpha, beta)), тоді як просто довжина дає функцію як конуса, недиференційовану в точці мінімуму. Брр. Квадрат зручніший.

Очевидно, що помилка мінімізується, коли вектор eортогональний площині, натягнутій на вектори. iі j.

Ілюстрація

Іншими словами: ми шукаємо таку пряму, що сума квадратів довжин відстаней від усіх точок до цієї прямої мінімальна:

UPDATE: тут у мене одвірок, відстань до прямої має вимірюватися по вертикалі, а не ортогональною проекцією. Ось цей коментатор має рацію.

Ілюстрація

Зовсім іншими словами (обережно, погано формалізовано, але на пальцях має бути ясно): ми беремо всі можливі прямі між усіма парами точок і шукаємо середню пряму між усіма:

Ілюстрація

Інше пояснення на пальцях: ми прикріплюємо пружинку між усіма точками даних (тут у нас три) і пряме, що ми шукаємо, і пряма рівноважного стану є саме те, що ми шукаємо.

Мінімум квадратичної форми

Інакше кажучи, ми шукаємо такий вектор x=(alpha, beta), що:

Нагадую, цей вектор x=(alpha, beta) є мінімумом квадратичної функції ||e(alpha, beta)||^2:

Тут не зайвим буде згадати, що матрицю можна інтерпретувати у тому числі як і квадратичну форму, наприклад, одинична матриця ((1,0),(0,1)) може бути інтерпретована як функція x^2 + y^2:

квадратична форма

Вся ця гімнастика відома під ім'ям лінійної регресії.

Рівняння Лапласа з граничною умовою Діріхле

Початковий коміт доступний. Для мінімізації зовнішніх залежностей я взяв код свого софтверного рендерера вже на хабрі. Для вирішення лінійної системи я користуюся OpenNL, це відмінний солвер, який, щоправда, дуже складно встановити: потрібно скопіювати два файли (.h+.c) у папку з вашим проектом. Все згладжування робиться наступним кодом:

For (int d=0; d<3; d++) { nlNewContext(); nlSolverParameteri(NL_NB_VARIABLES, verts.size()); nlSolverParameteri(NL_LEAST_SQUARES, NL_TRUE); nlBegin(NL_SYSTEM); nlBegin(NL_MATRIX); for (int i=0; i<(int)verts.size(); i++) { nlBegin(NL_ROW); nlCoefficient(i, 1); nlRightHandSide(verts[i][d]); nlEnd(NL_ROW); } for (unsigned int i=0; i&face = faces[i]; for (int j = 0; j<3; j++) { nlBegin(NL_ROW); nlCoefficient(face[ j ], 1); nlCoefficient(face[(j+1)%3], -1); nlEnd(NL_ROW); } } nlEnd(NL_MATRIX); nlEnd(NL_SYSTEM); nlSolve(); for (int i=0; i<(int)verts.size(); i++) { verts[i][d] = nlGetVariable(i); } }

X, Y та Z координати відокремлені, я їх згладжую окремо. Тобто, я вирішую три системи лінійних рівнянь, кожне має кількість змінних рівною кількістю вершин у моїй моделі. Перші n рядків матриці A мають лише одну одиницю на рядок, а перші n рядків вектора b мають оригінальні координати моделі. Тобто, я прив'язую по пружинці між новим становищем вершини і старим становищем вершини - нові не повинні занадто далеко йти від старих.

Всі наступні рядки матриці A (faces.size()*3 = кількості ребер всіх трикутників у сітці) мають одне входження 1 та одне входження -1, причому вектор b має нульові компоненти навпаки. Це означає, що я вішаю пружинку на кожне ребро нашої трикутної сітки: всі ребра намагаються отримати одну й ту саму вершину як відправну та фінальну точку.

Ще раз: змінними є всі вершини, причому вони можуть далеко відходити від початкового становища, але заодно намагаються стати схожими друг на друга.

Ось результат:

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

For (int i=0; i<(int)verts.size(); i++) { float scale = border[i] ? 1000: 1; nlBegin(NL_ROW); nlCoefficient(i, scale); nlRightHandSide(scale*verts[i][d]); nlEnd(NL_ROW); }

У нашій матриці A я для вершин, що знаходяться на краю, не додаю рядок з розряду v_i = verts[i][d], а 1000*v_i = 1000*verts[i][d]. Що це змінює? А змінює це нашу квадратичну форму помилки. Тепер одиничне відхилення від вершини краю коштуватиме не одну одиницю, як раніше, а 1000*1000 одиниць. Тобто, ми повісили сильнішу пружинку на крайні вершини, рішення воліє розтягнути інші. Ось результат:

Давайте вдвічі посилимо пружинки між вершинами:
nlCoefficient (face [j], 2); nlCoefficient(face[(j+1)%3], -2);

Логічно, що поверхня стала гладкішою:

А тепер ще в сто разів сильніше:

Що це? Уявіть, що ми вмочили дротяне кільце в мильну воду. У результаті мильна плівка, що утворилася, намагатиметься мати найменшу кривизну, наскільки це можливо, торкаючись-таки кордону - нашого дротяного кільця. Саме це ми й отримали, зафіксувавши кордон та попросивши отримати гладку поверхню всередині. Вітаю вас, ми тільки-но вирішили рівняння Лапласа з граничними умовами Діріхле. Круто звучить? А насправді лише одну систему лінійних рівнянь вирішити.

Рівняння Пуассона

Припустимо, що у мене є така картинка:

Всім гарна, тільки стілець мені не подобається.

Розріжу картинку навпіл:

І виділю руками стілець:

Потім все, що біле в масці, притягну до лівої частини картинки, а заразом по всій картинці скажу, що різниця між двома сусідніми пікселями повинна дорівнювати різниці між двома сусідніми пікселями правої картинки:

For (int i=0; i

Ось результат:

Код та зображення доступні