2011-10-04 28 views
6

Tôi đang cố gắng viết một chương trình nội suy spline khối. Tôi đã viết chương trình nhưng, biểu đồ không được phát ra chính xác. Các spline sử dụng điều kiện biên tự nhiên (thứ hai dervative lúc bắt đầu/kết thúc nút là 0). Mã này nằm trong Matlab và được hiển thị bên dưới,Chương trình Spline khối

clear all 
%Function to Interpolate 
k = 10;     %Number of Support Nodes-1 
xs(1) = -1; 
for j = 1:k 
    xs(j+1) = -1 +2*j/k; %Support Nodes(Equidistant) 
end; 
fs = 1./(25.*xs.^2+1);  %Support Ordinates 
x = [-0.99:2/(2*k):0.99]; %Places to Evaluate Function 
fx = 1./(25.*x.^2+1);  %Function Evaluated at x 

%Cubic Spline Code(Coefficients to Calculate 2nd Derivatives) 

f(1) = 2*(xs(3)-xs(1)); 
g(1) = xs(3)-xs(2); 
r(1) = (6/(xs(3)-xs(2)))*(fs(3)-fs(2)) + (6/(xs(2)-xs(1)))*(fs(1)-fs(2)); 
e(1) = 0; 

for i = 2:k-2 
    e(i) = xs(i+1)-xs(i); 
    f(i) = 2*(xs(i+2)-xs(i)); 
    g(i) = xs(i+2)-xs(i+1); 
    r(i) = (6/(xs(i+2)-xs(i+1)))*(fs(i+2)-fs(i+1)) + ... 
      (6/(xs(i+1)-xs(i)))*(fs(i)-fs(i+1)); 
end 
e(k-1) = xs(k)-xs(k-1); 
f(k-1) = 2*(xs(k+1)-xs(k-1)); 
r(k-1) = (6/(xs(k+1)-xs(k)))*(fs(k+1)-fs(k)) + ... 
     (6/(xs(k)-xs(k-1)))*(fs(k-1)-fs(k)); 

%Tridiagonal System 

i = 1; 
A = zeros(k-1,k-1); 
while i < size(A)+1; 
    A(i,i) = f(i); 
    if i < size(A); 
     A(i,i+1) = g(i); 
     A(i+1,i) = e(i); 
    end 
    i = i+1; 
end 

for i = 2:k-1        %Decomposition 
    e(i) = e(i)/f(i-1); 
    f(i) = f(i)-e(i)*g(i-1); 
end 

for i = 2:k-1        %Forward Substitution 
    r(i) = r(i)-e(i)*r(i-1); 
end 

xn(k-1)= r(k-1)/f(k-1); 
for i = k-2:-1:1       %Back Substitution 
    xn(i) = (r(i)-g(i)*xn(i+1))/f(i); 
end 

%Interpolation 

if (max(xs) <= max(x)) 
    error('Outside Range'); 
end 

if (min(xs) >= min(x)) 
    error('Outside Range'); 
end 


P = zeros(size(length(x),length(x))); 
i = 1; 
for Counter = 1:length(x) 
    for j = 1:k-1 
     a(j) = x(Counter)- xs(j); 
    end 
    i = find(a == min(a(a>=0))); 
    if i == 1 
     c1 = 0; 
     c2 = xn(1)/6/(xs(2)-xs(1)); 
     c3 = fs(1)/(xs(2)-xs(1)); 
     c4 = fs(2)/(xs(2)-xs(1))-xn(1)*(xs(2)-xs(1))/6; 
     t1 = c1*(xs(2)-x(Counter))^3; 
     t2 = c2*(x(Counter)-xs(1))^3; 
     t3 = c3*(xs(2)-x(Counter)); 
     t4 = c4*(x(Counter)-xs(1)); 
     P(Counter) = t1 +t2 +t3 +t4; 
    else 
     if i < k-1 
     c1 = xn(i-1+1)/6/(xs(i+1)-xs(i-1+1)); 
     c2 = xn(i+1)/6/(xs(i+1)-xs(i-1+1)); 
     c3 = fs(i-1+1)/(xs(i+1)-xs(i-1+1))-xn(i-1+1)*(xs(i+1)-xs(i-1+1))/6; 
     c4 = fs(i+1)/(xs(i+1)-xs(i-1+1))-xn(i+1)*(xs(i+1)-xs(i-1+1))/6; 
     t1 = c1*(xs(i+1)-x(Counter))^3; 
     t2 = c2*(x(Counter)-xs(i-1+1))^3; 
     t3 = c3*(xs(i+1)-x(Counter)); 
     t4 = c4*(x(Counter)-xs(i-1+1)); 
     P(Counter) = t1 +t2 +t3 +t4; 
     else 
     c1 = xn(i-1+1)/6/(xs(i+1)-xs(i-1+1)); 
     c2 = 0; 
     c3 = fs(i-1+1)/(xs(i+1)-xs(i-1+1))-xn(i-1+1)*(xs(i+1)-xs(i-1+1))/6; 
     c4 = fs(i+1)/(xs(i+1)-xs(i-1+1)); 
     t1 = c1*(xs(i+1)-x(Counter))^3; 
     t2 = c2*(x(Counter)-xs(i-1+1))^3; 
     t3 = c3*(xs(i+1)-x(Counter)); 
     t4 = c4*(x(Counter)-xs(i-1+1)); 
     P(Counter) = t1 +t2 +t3 +t4; 
     end  
    end 
end 

P = P'; 
P(length(x)) = NaN; 

plot(x,P,x,fx) 

Khi tôi chạy mã, hàm nội suy không đối xứng và không hội tụ chính xác. Bất cứ ai có thể cung cấp bất kỳ đề xuất về các vấn đề trong mã của tôi? Cảm ơn.

Trả lời

9

Tôi đã viết một gói spline khối trong Mathematica một thời gian dài trước đây. Đây là bản dịch của tôi về gói đó vào Matlab. Lưu ý tôi đã không nhìn vào splines khối trong khoảng 7 năm, vì vậy tôi căn cứ này tắt tài liệu của riêng tôi. Bạn nên kiểm tra mọi thứ tôi nói.

Vấn đề cơ bản là chúng tôi được cung cấp n điểm dữ liệu (x(1), y(1)) , ... , (x(n), y(n)) và chúng tôi muốn tính toán một nội suy khối piecewise. Các interpolant được định nghĩa là

S(x) = { Sk(x) when x(k) <= x <= x(k+1) 
      { 0  otherwise 

Đây Sk (x) là một đa thức khối có dạng

Sk(x) = sk0 + sk1*(x-x(k)) + sk2*(x-x(k))^2 + sk3*(x-x(k))^3 

Các tính chất của spline là:

  1. các spline vượt qua qua các dữ liệu điểm Sk(x(k)) = y(k)
  2. Đường spline liên tục tại điểm cuối và do đó liên tục ở mọi nơi trong khoảng cách nội suy Sk(x(k+1)) = Sk+1(x(k+1))
  3. Các spline có liên tục phái sinh đầu tiên Sk'(x(k+1)) = Sk+1'(x(k+1))
  4. Các spline có liên tục thứ hai bắt nguồn từ Sk''(x(k+1)) = Sk+1''(x(k+1))

Để xây dựng một spline khối từ một tập hợp các điểm dữ liệu chúng ta cần phải giải quyết cho các hệ số sk0, sk1, sk2sk3 cho mỗi một trong các đa thức khối n-1. Đó là tổng số 4*(n-1) = 4*n - 4 các ẩn số. Bất động sản 1 cung cấp n ràng buộc, và tài sản 2,3,4 mỗi cung cấp thêm n-2 ràng buộc. Do đó chúng tôi có các ràng buộc n + 3*(n-2) = 4*n - 64*n - 4 các ẩn số. Điều này để lại hai bậc tự do. Chúng tôi sửa các mức độ tự do này bằng cách đặt đạo hàm bậc hai bằng 0 ở các nút bắt đầu và kết thúc.

Hãy để m(k) = Sk''(x(k)), h(k) = x(k+1) - x(k)d(k) = (y(k+1) - y(k))/h(k). Sau đây ba hạn mối quan hệ tái giữ

h(k-1)*m(k-1) + 2*(h(k-1) + h(k))*m(k) + h(k)*m(k+1) = 6*(d(k) - d(k-1)) 

các m (k) là ẩn số chúng ta muốn giải quyết cho. h(k)d(k) được xác định bởi dữ liệu đầu vào. Mối quan hệ lặp lại ba kỳ này xác định một hệ thống tuyến tính ba chiều. Khi m(k) được xác định các hệ số cho Sk được đưa ra bởi

sk0 = y(k) 
    sk1 = d(k) - h(k)*(2*m(k) + m(k-1))/6 
    sk2 = m(k)/2 
    sk3 = m(k+1) - m(k)/(6*h(k)) 

Được rồi đó là tất cả các môn toán bạn cần biết để hoàn toàn xác định các thuật toán để tính toán một spline khối.Dưới đây là trong Matlab:

function [s0,s1,s2,s3]=cubic_spline(x,y) 

if any(size(x) ~= size(y)) || size(x,2) ~= 1 
    error('inputs x and y must be column vectors of equal length'); 
end 

n = length(x) 

h = x(2:n) - x(1:n-1); 
d = (y(2:n) - y(1:n-1))./h; 

lower = h(1:end-1); 
main = 2*(h(1:end-1) + h(2:end)); 
upper = h(2:end); 

T = spdiags([lower main upper], [-1 0 1], n-2, n-2); 
rhs = 6*(d(2:end)-d(1:end-1)); 

m = T\rhs; 

% Use natural boundary conditions where second derivative 
% is zero at the endpoints 

m = [ 0; m; 0]; 

s0 = y; 
s1 = d - h.*(2*m(1:end-1) + m(2:end))/6; 
s2 = m/2; 
s3 =(m(2:end)-m(1:end-1))./(6*h); 

Dưới đây là một số mã để vẽ một spline khối:

function plot_cubic_spline(x,s0,s1,s2,s3) 

n = length(x); 

inner_points = 20; 

for i=1:n-1 
    xx = linspace(x(i),x(i+1),inner_points); 
    xi = repmat(x(i),1,inner_points); 
    yy = s0(i) + s1(i)*(xx-xi) + ... 
    s2(i)*(xx-xi).^2 + s3(i)*(xx - xi).^3; 
    plot(xx,yy,'b') 
    plot(x(i),0,'r'); 
end 

Đây là một chức năng xây dựng một spline khối và lô trong vào chức năng Runge nổi tiếng:

function cubic_driver(num_points) 

runge = @(x) 1./(1+ 25*x.^2); 

x = linspace(-1,1,num_points); 
y = runge(x); 

[s0,s1,s2,s3] = cubic_spline(x',y'); 

plot_points = 1000; 
xx = linspace(-1,1,plot_points); 
yy = runge(xx); 

plot(xx,yy,'g'); 
hold on; 
plot_cubic_spline(x,s0,s1,s2,s3); 

Bạn có thể nhìn thấy nó trong hành động bằng cách chạy lệnh sau tại Matlab nhắc

>> cubic_driver(5) 
>> clf 
>> cubic_driver(10) 
>> clf 
>> cubic_driver(20) 

Khi bạn có hai mươi nút, nội suy của bạn sẽ không thể phân biệt được với hàm Runge.

Một số nhận xét về mã Matlab: Tôi không sử dụng bất kỳ vòng lặp nào trong khi hoặc trong khi. Tôi có thể vector hóa tất cả các hoạt động. Tôi nhanh chóng tạo thành ma trận trianggonal thưa thớt với spdiags. Tôi giải quyết nó bằng cách sử dụng toán tử dấu gạch chéo ngược. Tôi đếm trên UMFPACK của Tim Davis để xử lý các giải pháp phân tích và tiến và lùi.

Hy vọng điều đó sẽ hữu ích. Đoạn mã có sẵn như là một ý chính trên github https://gist.github.com/1269709

Các vấn đề liên quan