Numerical Analysis — Interpolation
Xülasə: Çox vaxt mühəndislər elə problemlərlə üzləşirlər ki, harada onlara məlum olan yalnız müəyyən sayda x və y ədədlər çoxluğu olur. Bu zaman mühəndislər verilən çoxluğda x və y cütlərini analiz edib ortaya faydalı bir model çıxartmalıdırlar. Sözsüz bu model həqiqi finksiya ilə üst-üstə düşməyə də bilər lakin bilmədiyimiz həqiqi bir funksiyaya (modelə) yaxın bir funksiyanın alınması bir çox hallarda kifayət edir. Bu yazıda da əsas toxunulan məsələ Lagrangian Polynomial Interpolation, Chebyshev Interpolation, Piecewise Linear Interpolation, Cubic Interpolating Splines, The Least-squares Approximation və Runge’s phenomenon kimi fərqli metodlar vasitəsi ilə x və y çoxluqlarını analiz edərək ortaya mənalı bir model qoymaqdır. Yazıda geniş şəkildə MATLAB işləndiyi üçün daha öncəki yazını oxumağı məsləhət görürəm.
Önsöz
Biz artıq bundan əvvəlki yazılarda gördük ki, Taylor expansion vasitəsi ilə funksiyaya aid oxşar nəticəni verən çoxhədlini tapmaq olar və beləlikə təqribi cavab almaq olar. Taylor expansion funksiyaların təxminində çox güclü bir əlat olmasına baxmayaraq onun qurulması üçün çoxlu şərtlərə ehtiyac var, eyni zamanda o funksiyaları yalnız kiçik bir əhatə dairəsində təxmin edir və bu alverişsiz ola bilər. Digər hallarda isə biz ümumiyyətlə funksiyanın özünü bilmirik və bizə məluma olan yalnız həqiqi funksiyaya aid bəzi nöqtələrdir. Daha dəqiq olsaq bü nöqtələr x və y koordinatlarından ibarət n+1 sayda (əgər 0-dan n-dək saysaq) cüt yaradır, hansıları biri birindən fərqli x ədədlərindən ibarətdir və biz bu x ədədlərini node adlandırırıq.
Bu kimi hallarda, node-lardan keçən həqiqi funksiyanı bilməsək də, biz verilən node-lara əsasən təqribi funksiyanı tapa bilərik. Belə bir funksiyaya interpolant deyilir.
Interpolant-ların bir çox növləri var, məsələn polynomial interpolant, trigonometric (Fourier) interpolant, rational interpolant, lakin bu yazıda yalnız polynomial interpolant haqqında müzakirə aparacağıq.
Yuxarıda göstərilən polynomial interpolant-ın a əmsallarından (weight) xətti asıllığı var. Növbəti bölümlərdə biz daha ətraflı polynomial interpolant-ları və onların növlərini müzakirə edəcəyik.
Lagrangian Polynomial Interpolation
Teorem: İstənilən x və y cütlərindən ibarət çoxluq üçün {(x[i], y[i])}, harada x[i] biri birində fərqli node-lardır, elə bir həddi n və ya n-dən kiçik olan yeganə (unique) çoxhədli (polynomial) mövcuddur ki, hansını biz x[i] node-ların və hər node-a müvafiq y[i] dəyərlərin interpolating polynomial-ı adlandırıb Π[n] deyə işarəliyirik.
Əgər y[i] davamlı (continuous) f funksiyasının dəyərləridirsə, Π[n] f funksiyasının interpolating polynomial-ı adlandırılır (və ya f-in interpolant-ı) və aşağıda göstərildiyi kimi işarələnir.
Teorem-də mühum məqamlardan biri “yeganə (unique) çoxhədli (polynomial) mövcuddur” hissəsidir ki, bunun ispatını analiz etmək faydalı olar.
Proof by contradiction: Təsəvvür edək ki, teoremdəki formulanı ödəyən iki fərqli n hədli polynomial var Π[n] və Π[n]*. O zaman qoy G[n] polynomial-ı Π[n] − Π[n]* olsun. Bu halda G[n] = 0, çünki:
Beləliklə, G[n] polynomial-ında 0-ların sayı n+1 qədər oldu. Və n hədli polynomial-ın n+1 sayda 0 ola biləcəyi tək hal G[n] = 0. Nəticədə hər iki polynomial identifikdir (identical):
Bu haqda daha geniş ispatı video 1 və video 2-dən izləyə bilərsiniz. Π[n] tam formasın almaq üçün ilk öncə y[i]-dan başlayaq, hansı i = k və y[k] = 1 şərtindən başqa (k sabit ədəddir), bütün i dəyərləri üçün 0-a bərabər olur (vanish).
Daha sonra Kronecker symbol-dan istifadə edərək δ[jk] φ[k] funksiyasının nəticəsini təyin edək:
φ[k] funksiyasının formulası aşağıda göstərilib və funksiya Lagrange characteristic polynomials-dır deyə adlandırılır.
Daha açıq şəkildə yazsaq:
Ola bilsin ki, yuxarıda yazılan formulalar sizə qarışıq gəldi məhs bu səbəbdən faydalı olar ki, n = 2 götürərək kiçik bir misal üzərindən onları tətbiq edək:
y[i] və φ[k] bəlli olduqdan sonra aşağıda göstərilən Lagrangian interpolation polynomials-ı (və ya Lagrange form of the interpolant) alırıq.
Daha geniş şəkildə yazsaq:
Formula aydın olmayan kəslərə aşağıdakı misalı izləməyi məsləhət görürəm.
MATLAB-da Lagrangian interpolation polynomials-ı biz polyfit funksiyası vasitəsi ilə ala bilərik. Daxili ədədlər (input) olaraq n+1 sayda x və y ədədlərinin vektoru və polynomial-ın həddi (degree) n daxil etməliyik. Nəticədə funksiya bizə aşağıda göstərilən şəkildə polynomial-a məxsus əmsal (coefficient) vektoru qaytarır.
Yəni vektorda olan ilk coefficient polynomial-ın son dəyişəninə məxsusdur. Daha sonra polyval əməliyyatı vasitəsi ilə coefficient vektorunu və x ədədlərini ötürərək qurduğumuz polynomial-ı dəyərləndirə bilərik (polynomial qrafında hər ötürülən x ədədinə müvafiq olaraq ona uyğun y ədədinin alınması).
c = polyfit(x, y, n)
y_plot = polyval(c, x_plot)Interpolation error
Qoy I qapalı interval olsun və x[i] I intervalında biri birindən fərqli n+1 sayda interpolation node-lar. Eyni zamanda, qoy f funksiyasının I interval boyunca n+1 order-dək davamlı (continuous) törəməsi olsun. O zaman, ∀x ∈ I ( I intervalına məxsus bütün x-lər) üçün ∃ξ ∈ I (I intervalında elə bir ξ ədədi mövcuddur) ki, aşağıdakı formula doğrudur:
Aydın məsələdir ki, həqiqi funksiya f və f-in interpolant-ı olan Π[n]f node nöqtələrində eyni dəyər alırlar, lakin bu node-lardan kənar funksiyanın hər hansı bir hissəsi üçün mütləq doğru deyil:
Verilən h > 0 və x[0] üçün node-ları biri birində eyni məsafədə yerləşdirsək (uniform distribution):
Daha aydın formula alarıq.
Sonuncu aldığımız bərabərsizliyin sağ tərəfi maksimal error-un göstəricisidir. n sonsuzluğa yaxınlaşdıqca n → ∞ bərabərsizliyin qırmızı hissəsi 0-a yaxınlaşır hansı ki, bizə sərf edir çünki error azalır. Eyni zamanda n → ∞ oldquda bərabərsizliyin göy tərəfinin özünü necə aparacağı bir başa funksiyadan aslıdır. Bu halda bizim 3 variantımız var. Göy tərəf 0-yaxınlaşır hansı ki, yaxşıdır, göy tərəf sabit c ədədidir hansı ki, yenə də yaxşıdır, çünki qırmızı tərəf 0-a yaxınlaşdıqca error yenə də azalır (hətda c sabit olsa da), və sonuncu variant göy tərəfin ∞ yaxınlaşmasıdır ki, burada artıq formula analiz olunmalıdır. Formulanın qırmızı tərəfi 0-a daha tez yaxınlaşır sa, o zaman error azalır, yox əgər formulanın göy tərəfi ∞ daha tez yaxınlaşır error artır.
Aşağıdakı funksiyanı nəzərə alaraq
a) funksiyaya aid eyni məsafəli node-lar seçərək (uniform distribution) interpolant-ın 2, 4, 6, 8 dərəcələrində Lagrange polynomial-ı tapın. Həqiqi funksiyanı və funksiyanın interpolant-ının qraflarını çəkin.
b) n=2, 4, 6, 8 götürərək yaranan interpolation xətasını dəyərləndirin. Xətanı qrafda göstərin.
clear, close all, clc% həqiqi funksiya
f = @(x) x.*sin(x);% interval
I = [-2, 6];% a)% node-ların sayı
n = [2, 4, 6, 8]% for loop-da hər node sayına uyğun qrafın çəkilməsi
for i = 1:length(n)
% intervalda 0-dan n-dək n+1 sayda eyni məsafəli node-lar
x_nodes = linspace(I(1), I(2), n(i) + 1);
y_nodes = f(x_nodes); % Lagrange polynomial coefficient-ləri
c = polyfit(x_nodes, y_nodes, n(i)); % qrafı çəkmək üçün 1000 sayda x və y nöqtələri
x_graph = linspace(I(1), I(2), 1000);
y_graph = f(x_graph); % interpolant-a məxsus y dəyərləri
y_interp = polyval(c, x_graph); figure; % əsl funksiyanı --, interpolant-ı davamlı xətt ilə çəkilməsi
% və iterpolat-ın node-larının o ilə qrafda işarələnməsi
plot(x_graph, y_graph, '--', x_graph, y_interp, x_nodes, y_nodes, 'o'); %qrafın daha aydın görsənməsi üçün qıraq intervallarda boşluq
xlim([I(1) - 0.12, I(2) + 0.12]);% yalnız a) misalı üçün `end` uncomment edin
% end
MATLAB-da aldığımızı qraflardan görürük ki, node-ların sayı n artdıqca funksiyanın interpolant-ı daha da dəqiq nəticə göstərir (xəta azalır).
% b)% daha öncə interpolation zamanı xəta formulanı tətbiq edərək
% f funksiyasının hər seçdiyimiz n-ə nisbətən törəməsinin
% maksimal dəyərini hesablamalıyıq
if (n(i) == 2)
% n+1-ci törəmə = 3 və funksiyanın 3-cü dərəcli törəməsinin
% −3sin(x)−xcos(x) aldığı ən böyük ədədin absolutu 9-dur
f_der_max_abs = 9elseif (n(i) == 4)
f_der_max_abs = 11elseif (n(i) == 6)
f_der_max_abs = 13elseif (n(i) == 8)
f_der_max_abs = 15end% uniform distribution olduğu üçün istənilən ardıcıl x-in fərqi = h
h = x_nodes(2) - x_nodes(1);% error esitmate, bu errorun interpolation zamanı ən çox ala
% biləcəyi ədəddir və yuxarıda göstərilən formulaya əsaslanır
err_est = h^(n(i) + 1)/(4*(n(i) + 1)) * f_der_max_abs;% error-un hesablanması, həqiqi funksiyanın y dəyərlərinin və
% funksiyanın interpolant-ının y dəyərlərinin fərqi
err = abs(y_graph - y_interp);figure;% error qrafının çəkilməsi
plot(x_graph, err);hold on;% error-un ala biləcəyi ən üst xətt (upper bound)
plot(x_graph, err_est * ones(size(x_graph)), 'r')% daha öncə a) misalında açılan for loop-un sonu
end
Xəta qraflardan biz iki vacib məqamı müşahidə edirik. n sayı artıqca xəta azalır (xətanın maksimal limiti də azalır) və xətanın interval boyunca uniform (bərabər paylanmış) olmaması. Daha spesifik olsaq bütün hallarda həqiqi qrafın qıraq nöqtələrində (sağ və sol) xətanın göstəricisi artır.
Runge’s phenomenon
Bəzən elə hallar olur ki, biz funksiyanın və node-ları uniformly distributed olan interpolant-ın qraflarını analiz etdikdə interpolant-da həqiqi funksiyanın qıraq nöqtələrinə yaxın yırğalanma (oscillation) müşahidə edirik.
Buna səbəb n → ∞ doğru getdiyi zaman (yəni node-ların sayı artdıqca) əsl funksiya və funksiyanın interpolant-ı arasında maksimal error-un artmasıdır, yəni daha öncə qeyd etdiyimiz formulada formulanın göy hissəsinin sonsuzluğa ∞ yaxınlaşmasının formulanın qırmızı hissəsinin 0-a yaxı yaxınlaşmasından daha tez baş verməsidir.
Aşağıdakı funksiyanı nəzərə alaraq
MATLAB vasitəsi ilə təsdiqləyin ki, biri birində eyni məsafədə olan node-ların sayı n sonsuzluğa yaxınlaşdıqca n → ∞, həqiqi funksiya ilə funksiyanın interpolant-ı arasında xəta artır.
clear, close all, clc% həqiqi funksiya
f = @(x) 1./(1 + x.^2);% interval
I = [-5, 5];% qrafı çəkmək üçün 1000 sayda x və y nöqtələri
x_graph = linspace(I(1), I(2), 1000);
y_graph = f(x_graph);% n = 1, 3, 5, 7, ..., 15
for n = 1:2:16
figure, hold on, box on % əsl funksiyanın qara rəngdə qrafı
plot(x_graph, y_graph, 'k-', 'LineWidth', 1.2) % koordinat oxunun əlavə dizaynı (vacib deyil)
axis([-5.1 5.1 -0.4 1.2]) % intervalda 0-dan n-dək n+1 sayda eyni məsafəli node-lar
x_nodes = linspace(I(1), I(2), n + 1);
y_nodes = f(x_nodes); % Lagrange polynomial coefficient-ləri
c = polyfit(x_nodes, y_nodes, n); % interpolant-a məxsus y dəyərləri
y_interp = polyval(c, x_graph); % funksiyanın interpolant-nın qırmızı qənqdə qrafı
plot(x_graph, y_interp, 'r-', 'LineWidth', 1.2) % press any key to continue
pauseend
Qraflardan görünür ki, funksiyanın interpolant-ı node-ların sayı artdıqca qrafın mərkəzində həqiqi funksiyaya yaxınlaşır. Lakin qrafın mərkəzindən fərqli olaraq qrafın kənar hissələrində node-ların sayı artdıqca yırğalanma (oscillation) baş verir və buna səbəb Runge’s phenomenon-dur.
Chebyshev Interpolation
Bundan əvvəl biz Lagrange interpolation-nun arzuolunmaz effektini, yəni Runge’s phenomenon-la tanış olduq. Bu problemi aradan qaldırmaq üçün biz node-ları bərabər məsafəli (uniform distribution) götürmək əvəzinə aşağıda göstərilən formulaya asasən götürə bilərik.
Bu formada seçilən node-ları biz Chebyshev node-ları adlandırırıq. Chebyshev node-ların əsas özəlliyi ondadır ki, qrafın qıraq nöqtələrinə yaxınlaşdıqca node-lar biri birinə daha sıx yerləşir (node-ların arasındakı məsafə kiçilir).
Daha öncəki Runge’s phenomenon problemi olan məsələdə verilən funksiyanı Chebyshev node-lar vasitəsi ilə hesablayın.
clear, close all, clc% həqiqi funksiya
f = @(x) 1./(1 + x.^2);% interval
I = [-5, 5];% qrafı çəkmək üçün 1000 sayda x və y nöqtələri
x_graph = linspace(I(1), I(2), 1000);
y_graph = f(x_graph);figure;% node-lar 1, 2, 4, ..., 32 olanda
for n = [1 2 4 8 16 32]
% Chebyshev nodes formulasındakı iterasiya
i = 0:n; % Chebyshev nodes formulasındakı x hat
x_hat = -cos(pi*i/n); % Chebyshev nodes formulasındakı x və y ədədləri
x_nodes = 0.5 * (I(1) + I(2)) + 0.5*(I(2) - I(1)) * x_hat;
y_nodes = f(x_nodes); % Chebyshev polynomial coefficient-ləri
c = polyfit(x_nodes, y_nodes, n); % interpolant-a məxsus y dəyərləri
y_interp = polyval(c, x_graph); % əsl funksiyanı qara, interpolant-ı isə qırmızı davamlı
% xətt ilə çəkilməsi və iterpolat-ın node-larının
% `x` ilə qrafda işarələnməsi
plot(x_graph, y_graph, 'k-', x_graph, y_interp, 'r-', x_nodes, y_nodes, 'rx', 'LineWidth', 2, 'MarkerSize', 8) % press any key to continue
pauseend
Piecewise Linear Interpolation
Chebyshev nodes hamar funksiyalar üçün kifayət qədər yaxşı nəticə göstərir. Lakin fikir verdinizsə Chebyshev interpolation zamanı node-ları hesablamaq üçün ya biz həqiqi funksiyanı bilməliyik, ya da bizə əvvəlcədən verilən node-lar və onların dəyərləri interpolate olunacaq funksiyanın Chebyshev node-ları ilə üst üstə düşsün. Sözsüz funksiya hər zaman hamar olmur və ya hər zaman əvvəlcədən bəlli olmur ki, biz onun Chebyshev node-larını hesablayaraq interpolate edək. Bu zaman Runge problemininə digər həll yolu kimi piecewise linear interpolation aşağıdakı formulaya uyğun hesablaya bilərik.
Daha dəqiq olsaq piecewise linear interpolation üçün node-ların uniformly distributed olmaları vacib deyil. Formulada I iki ardıcıl node-un aralığıdır və itnerpolation-un əsas prinsipi iki ardıcıl nodu düz xətlə birləşdirməsidir.
Piecewise linear interpolation-un işarəsindəki H I intervalları arasında ən maksimalını göstərir.
Əgər n = 1 və h = H götürsək, üstəlik f funksiyasının interval boyu ikinci dərəcəli törəməsi mövcuddursa, o zaman piecewise linear interpolation üçün error estimate aşağıdakı kimi olacaq.
MATLAB-da piecewise linear interpolation interp1 funksiyası vasitəsi ilə hesablanır.
y_interp = interp1(x_nodes, y_nodes, x_graph);Daha öncəki Runge’s phenomenon problemi olan məsələdə verilən funksiyanı
interp1istifadə edərək piecewise linear interpolation-ı hesablayın. n = 1, 2, 4, 8, 16, 32 götürərək interpolant-ın qrafını çəkin. Yaranan xətanın (error) infinity norm-unu hesablayın və göstərin ki, iki node aralığı məsafəni h olduğunu nəzərə alaraq interpolant kvadratik şəkildə həqiqi həllə yaxınlaşır (converge).
clear, close all, clc% həqiqi funksiya
f = @(x) 1./(1 + x.^2);% interval
I = [-5, 5];% qrafı çəkmək üçün 1000 sayda x və y nöqtələri
x_graph = linspace(I(1), I(2), 1000);
y_graph = f(x_graph);% n = 1, 2, ..., 32
n_nodes = [1 2 4 8 16 32];figure;for i = 1:numel(n_nodes)
% hal hazırki iterasıyada node-ların sayı
n = n_nodes(i); % intervalda 0-dan n-dək n+1 sayda node-lar
x_nodes = linspace(I(1), I(2), n + 1);
y_nodes = f(x_nodes); % piecewise linear interpolant-a məxsus y dəyərləri
y_interp = interp1(x_nodes, y_nodes, x_graph); % əsl funksiyanı qara, interpolant-ı isə qırmızı davamlı
% xətt ilə çəkilməsi və iterpolat-ın node-larının
% `x` ilə qrafda işarələnməsi
plot(x_graph, y_graph, 'k-', x_graph, y_interp, 'r-', x_nodes, y_nodes, 'rx', 'LineWidth', 2, 'MarkerSize', 8) % hər node uyğun xətanın inf norm hesabı, vektora əlavə edilməsi
error(i) = max(abs(y_graph - y_interp)); % press any key to continue
pauseend
Yaranan xətanın (error) infinity norm-unun hesablanması
H = (I(2) - I(1))./n_nodes;figure% error-un H-ə nisbətən qrafı, hər n sayı qrafda `x` ilə işarələnib
loglog(H, error, 'bx-', 'LineWidth', 2, 'MarkerSize', 8)hold on, box on% kvadratik H-in adi H-ə nisbətən qrafı (yaşıl rəngdə)
loglog(H, H.^(2), 'g-', 'LineWidth', 2)% qrafın dizaynı
xlabel('h','FontSize', 16)
ylabel('error','FontSize', 16)
legend('error', 'O(h^2)', 'Location', 'se');
Qrafdan biz görürük ki, convergence order həqiqətən kvadratikdir.
Cubic Interpolating Splines
Piecewise linear interpolation mövcud olduğu kimi diqər n ≥ 2 dərəcəli piecewise polynomial interpolation-lar da mövcuddur, məsələn piecewise quadratic interpolation.
Digər sözlə desək piecewise quadratic interpolation hər I intervalında f funksiyanı onun kvadratik çoxhədlisi ilə əvəzləyir necə ki, piecewise linear interpolation düz xəttlərlə bu edir. Bu zaman əvəzlənən hissələrə spline deyilir, məsələn linear spline, quadratic spline və s. Eyni ilə piecewise linear və quadratic interpolation-ları təyin etdiyimiz kimi biz 3-cü dərəcəli piecewise polynomial interpolation-u da təyin edə bilərik, hansında interpolation 3-cü dərəcəli çoxhədlilərlə həyata keçirilir və interpolating cubic spline adlandırılır.
Yuxarda verilən şəkildə ardıcıl node-ları cubic spline-lar s[i] birləşdirir (qırmızı rəngdə). Interpolating cubic spline digər prinsipi iki spline arası keçidi bacardıqca hamar (smooth) etməkdir. Məhs bu səbəbdən bəzi şərtlər ödənilməlidir, hansılara biz matching conditions deyirik. Məsələn əgər qrafda x[0] soldan ilk node olaraq götürsək, o zaman s[0] spline-ı x[0]-dan başlayaraq digər node olan x[1]-dək olan ədədlərdən ibarətdir. Bu zama əgər fikir verdinizsə s[0] spline-nın son nöqtəsi olan x[1] node-u həm də s[1] spline-nin başlanqıc nöqtəsidir. Məntiqli olar ki, növbəti şərti (matching condition) uyğulayaq:
Bu iki spline arası keçidi daha smoot etmək üçün keçid node-unda spline-ların birinci və ikinci dərəcəli törəməsini götürərək növbəti şərtləri də almış olarıq:
Sözsüz bu şərtlər bütün spline-ların keçid node-ları üçün tətbiq edilir. O zaman, daha formal və geniş izah bu cür olacaq:
Teorem: [a, b] intervalında f funksiyası və aşağıda göstərilən şəkildə node çoxluğu verilib.
Bu zaman, f üçün verilən cubic spline interpolant s aşağıdakı şərtləri ödəyən funksiyadır.
- Hər alt.interval üçün s(x) cubic polynomial-dır
- Hər s(x) funksiyası node-larda aşağıda göstərilən şərti ödəməlidir (yəni hər s(x) x node-a məxsus y ədəd ilə nəticələnir)
- Keçid node-larda s(x) funksiyaları bərabərdir.
- Keçid node-larda s`(x) funksiyaları bərabərdir.
- Keçid node-larda s``(x) funksiyaları bərabərdir.
- Və sonda aşağıda göstərilən iki şərtlərdən biri ödənilməlidir:
- natural (free) interpolating cubic spline
2. clamped interpolating cubic spline
Daha geniş izahla tanış olmaq istəyənlər video 3-dən izləyə bilərlər. Daha parktiki misalı isə aşağıda qeyd olunan videodan tapmaq olar.
MATLAB-da cubic spline interpolation üçün spline funksiyası mövcuddur.
y_interp = spline(x_nodes, y_nodes, x_graph);Daha öncəki Runge’s phenomenon problemi olan məsələdə verilən funksiyanı
splineistifadə edərək piecewise polynomial interpolation-ı hesablayın. n = 1, 2, 4, 8, 16, 32 götürərək interpolant-ın qrafını çəkin.
clear, close all, clc% həqiqi funksiya
f = @(x) 1./(1 + x.^2);% interval
I = [-5, 5];% qrafı çəkmək üçün 1000 sayda x və y nöqtələri
x_graph = linspace(I(1), I(2), 1000);
y_graph = f(x_graph);% n = 1, 2, ..., 32
n_nodes = [1 2 4 8 16 32];figure;for i = 1:numel(n_nodes)
% hal hazırki iterasıyada node-ların sayı
n = n_nodes(i); % intervalda 0-dan n-dək n+1 sayda node-lar
x_nodes = linspace(I(1), I(2), n + 1);
y_nodes = f(x_nodes); % cubic spline interpolant-a məxsus y dəyərləri
y_interp = spline(x_nodes, y_nodes, x_graph); % əsl funksiyanı qara, interpolant-ı isə qırmızı davamlı
% xətt ilə çəkilməsi və iterpolat-ın node-larının
% `x` ilə qrafda işarələnməsi
plot(x_graph, y_graph, 'k-', x_graph, y_interp, 'r-', x_nodes, y_nodes, 'rx', 'LineWidth', 2, 'MarkerSize', 8) % press any key to continue
pauseend
The Least-squares Approximation
Biz artıq Lagrangian polynomial interpolation-un hər zaman effektiv olmadığını gördük və bu problemi piecewise linear interpolation və cubic interpolating splines ilə həll etməyə çalışdıq. Lakin bu metodların heç biri extrapolation üçün (əldə olunan məlumatlar əsasında gələcəyə doğru təxminlər etmək) yaramır, diqər sözlə desək əldə olunan data-dan verilən intervalın kənarında olan data-ları müəyyən etmək. Bunun üçün biz least-square approximation istifadə edirik.
Formal olaraq metodla tanış olaq.
Tutalım ki, müəyyən n+1 sayda x və y cütləri verilib, harada y x ədədinin f funksiyasının tətbiqi nəticəsində alınan dəyəridir. O zaman, verilən m ≥ 1 tam ədədi üçün (m ≪ n) biz aşağıdakı bərabərsizliyi ödəyən çoxhədli axtarırıq.
Bərabərsizliyin sol tərəfindəki f tilda funksiyası least-squares approximation adlandırılır ( hər ikisi f tilda və p m hədli çoxhədlidirlər).
Yuxarıda göstərilən f tilda funksiyasının a əmsalları bilinmir. Bərabərsizliyin verdiyi məna ondan ibarətdir ki, biz elə a əmsalların tapmalıyıq ki, harada çoxhədlinin x nöqtəsində aldığı dəyər ilə f tilda və həqiqiq funksiyanın həmən nöqtədə aldığı dəyərin y, fərqinin kvadratının cəmi ən kiçik olsun, yəni hər node-da mean square error ən kiçik olsun.
Sözsüz bu yuxarıda yazılan formulalar bir çox insanlar üçün mürəkkəb gələ bilər, məhs bu səbəbdən aşağıda verilən misala baxmağı məsləhət görürəm.
MATLAB-da least-squares approximation Lagrangian polynomial interpolation kimi polyfit və polyval funksiyaları vasitəsi ilə hesablanır. Faktiki olaraq m = n olduqda least-square polynomial Lagrangian polynomial ilə üst-üstə düşür.
Aşağıdakı funksiyanı nəzərə alaraq
node-ların sayın n = 10 götürərək least-sqaure approximation vasitəsi ilə polynomial-ın dərəcəsi m dəyişdirərək funksiyanı interpolate edin. Əməliyyatı vizual olaraq qrafda göstərin.
clear, close all, clc% həqiqi funksiya
f = @(x) abs(x - pi/12);% interval
I = [-1, 1];% qrafı çəkmək üçün 1000 sayda x və y nöqtələri
x_graph = linspace(I(1), I(2), 1000);
y_graph = f(x_graph);% n = 10 sayda node-lar
x_nodes = linspace(I(1), I(2), 10);
y_nodes = f(x_nodes);% m 2-dən 15-dək dəyişdir
for m = 2:1:13
% least-square əmsalların hesabla
a = polyfit(x_nodes, y_nodes, m); % f tilda ədədlərin al
f_tilda = polyval(a, x_graph); % əsl funksiyanı qara xət-xət, interpolant-ı isə qırmızı
% davamlı xətt ilə çəkilməsi və iterpolat-ın node-larının
% `O` ilə qrafda işarələnməsi
plot(x_graph, y_graph, '--', x_graph, f_tilda, 'r-', x_nodes, y_nodes, 'kO', 'LineWidth', 2, 'MarkerSize', 8) % press any key to continue
pauseend
Yekun
Beləliklə, bu yazıda approximation-un [a, b] intervalında həqiqi f funksiyasına yaxın bir funksiyanın tapılması olduğunu öyrəndik. Bu yaxın funksiya əvvəlcədən verilmiş x (node) və y ədədləri vasitəsi necə tapılması ilə tanış olduq. Əgər n+1 sayda node-lar biri birindən fərqlidirsə o zaman həmən node-lardan keçən polynomial-ın yeganə olduğunu isbat etdik. Node-ların uniform distribution zamanı sayı artdıqca mütləq olaraq interpolant-ın erroru-nun azalmamasına əmin olduq və bu problemi aradan qaldırmaq üçün uniform distribution əvəzinə Chebyshev node-lardan istifadə etdik. Runge’s phenomenon-un aradan qaldırılması üçün diqər analiz etdiyimiz metod piecewise linear interpolation oldu. Eyni zamanda piecewise polynomial interpolation zamanı düz xətlərin əvəzinə üçüncü dərəcəli çoxhədlidən də (cubic splines) istifadəni nəzərdən keçirdik. Verilən intervaldan kənar data-nı təxmin etmək üçün least-squares metodunu nəzərdən keçirdik hansında degree of polynomial m normalda node-ların sayı n-dan daha az götürülür və əsas prinsipi mean-square error-u azaltmaqda bağlıdır. Eyni zamanda least-squares approximation zamanı m = n olduqda biz lagrangian polynomial interpolation-u aldığımızı praktik şəkildə gördük.
İstinad
Quarteroni, A., Saleri, F., Scientific Computing with MATLAB and Octave.
Sonda, mənə ADA Universitetində “Calculus 1” və “Calculus 2” kurslarını tədris etmiş Prof. Fuad Hacıyevə və Politecnico di Milano universitetində “Numerical Analysis” kursunu tədris etmiş Prof. Simona Perotto və TA Nicola Ferro-ya öz təşəkkürümü bildirirəm.
