% % % XeLatex Compiler. % % % % כל המקיים נפש אחת מעלין עליו כאילו קיים עולם מלא \documentclass[oneside,UTF8]{article} % ---------------------------------------- % ---------------------------------------- % ---------------------------------------- \usepackage{geometry} \usepackage{fancyhdr} \usepackage[heading=true]{ctex} \usepackage{multicol} \usepackage{datetime} \usepackage[fontsize=12pt]{fontsize} \usepackage{xcolor} \usepackage{hyperref} \usepackage{marvosym} \usepackage{ amsmath, amssymb, mathrsfs } \usepackage{caption} \usepackage{bm} \usepackage{float} \usepackage{graphicx} \usepackage{ booktabs, diagbox, multirow } \usepackage{setspace} \usepackage{listings} \usepackage{lettrine} \usepackage{lipsum} \usepackage{cjhebrew} \usepackage{tikz} % ---------------------------------------- % ---------------------------------------- % ---------------------------------------- \linespread{1.5} \geometry{ a4paper, left = 3.18cm, right = 3.18cm, top = 2.54cm, bottom = 2.5cm } % ---------------------------------------- \lstset{ extendedchars=false, columns = flexible, breaklines, showstringspaces = false, basicstyle = \normalsize, numbers = left, numberstyle = \tiny, keywordstyle = \color{ blue!70}, commentstyle = \color{red!50!green!50!blue!50}, frame = shadowbox, rulesepcolor = \color{ red!20!green!20!blue!20}, xleftmargin=2em,xrightmargin=2em, aboveskip=1em,belowskip=1em, framexleftmargin=2em,framexrightmargin=2em, language = C } % ---------------------------------------- \hypersetup{ colorlinks=true, linkcolor=cyan, % linkcolor=black, filecolor=blue, % urlcolor=red, citecolor=cyan, } % ---------------------------------------- \captionsetup[table]{labelfont={bf},labelformat={default},font={bf,normalsize},labelsep=space,name={Table}} \captionsetup[figure]{labelfont={bf},labelformat={default},font={bf,normalsize},labelsep=default,name={Figure}} % ---------------------------------------- \numberwithin{figure}{section} \numberwithin{table}{section} \numberwithin{equation}{section} % ---------------------------------------- \CTEXsetup[name={,.},number={\Roman{section}}]{section} \CTEXsetup[format={\Large\bfseries}]{section} % ---------------------------------------- \renewcommand\contentsname{\hfill Contents \hfill} \newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} \newcommand*{\ttiny}{\fontsize{3pt}{3.4}\selectfont} \newcommand*{\rightup}{\textsuperscript} \newcommand*{\ucite}[1]{\textsuperscript{\cite{#1}}} \renewcommand{\headrule}{\hbox to \headwidth{\color{red!20!green!20!blue!20} \leaders \hrule height \headrulewidth \hfill}} % ---------------------------------------- \newcommand*{\purple}{\color{red!200!green!20!blue!20}} \newcommand*{\gray}{\color[rgb]{0.5 0.5 0.5}} \newcommand*{\red}{\color[rgb]{1 0 0}} \newcommand*{\shallowRed}{\color[rgb]{1 0.2 0.5}} \newcommand*{\shallowBlue}{\color[rgb]{0 0.98 0.93}} \newcommand*{\shallowYellow}{\color[rgb]{1 0.9 0.6}} \definecolor{shallowRed}{rgb}{1 0.2 0.5} \definecolor{shallowGreen}{rgb}{0.88 0.93 0.85} \definecolor{shallowYellow}{rgb}{1 0.9 0.6} \definecolor{shallowBlue}{rgb}{0 0.98 0.93} % ---------------------------------------- % ---------------------------------------- % ---------------------------------------- \title{求解样条插值小区间上三次多项式系数算法} \author{$\rm Illusionna^{\href{https://Illusionna.readthedocs.io/}{\textrm{\Letter}}}$} \date{\tt\small\xxivtime,\ \today} % ---------------------------------------- % ---------------------------------------- % ---------------------------------------- \begin{document} % ---------------------------------------- \maketitle \vspace*{-15em} \begin{tikzpicture} \node at (15.5,0){ \shallowRed\huge\href{ https://github.com/Illusionna/Illusion }{$\bm\aleph$} }; \draw [white] (0,0) -- (0,0); \end{tikzpicture} \setcounter{page}{1} \pagenumbering{arabic} \fancyhead[L]{\purple\rightmark} \fancyhead[R]{} \fancyhead[C]{} \fancyfoot[C]{\normalsize--\ \thepage\ --} \thispagestyle{fancy} \vspace*{12em} \begin{spacing}{1.5} \tableofcontents \end{spacing} % ---------------------------------------- % ---------------------------------------- % ---------------------------------------- \pagestyle{fancy} % ---------------------------------------- % ---------------------------------------- % ---------------------------------------- \section{\songti 源} 算法出自于这本书：Burden, Annette and Burden, Richard and Faires, J. Numerical Analysis, 9th ed. (2010). 样条插值原理见下面网页，网址太长了，笔者拆开后注意某些文件夹名称中含空格，如果依然搜不到，直接搜主页，然后自行找找. https://Illusionna.readthedocs.io/zh/latest/projects/ Mathematics/Numerical Analysis/三点三次自然样条插值/Spline.html 主页：https://Illusionna.readthedocs.io 以下所有算法符号以及代码按照网页原理中统一. \section{\songti 算法} Input: $\bm{\vec{x}}=(x_0,x_1,x_2,\ldots,x_n)$, $\bm{\vec{y}}=(y_0,y_1,y_2,\ldots,y_n)$, 点列按照自变量从小到大已经排序好了. Output: $\forall k,\ a_k,b_k,c_k,d_k$. \[ \forall x\in[x_{k-1},x_k],\ \ s_k(x)=a_k+b_kx+c_kx^2+d_kx^3,\ \ k=1,2,\ldots,n \] \textbf{Step 1:} 计算步长并存储在步长数组里. \[ {\rm for}\ k,\ {\rm stepArray}_{k}=\bm{\vec{x}}_{k+1}-\bm{\vec{x}}_{k} \] \textbf{Step 2:} 计算 $\alpha$ 并存在 $\alpha{\rm Array}$ 数组里. \[ {\rm for}\ k,\ \alpha{\rm Array}_{k}=\dfrac{3}{{\rm stepArray}_k}\times(\bm{\vec{y}}_{k+1}-\bm{\vec{y}}_k)-\dfrac{3}{{\rm stepArray}_{k-1}}\times(\bm{\vec{y}}_{k}-\bm{\vec{y}}_{k-1}) \] \textbf{Step 3:} 给 $l{\rm Array},\mu{\rm Array},z{\rm Array}$ 数组首索引元素设置初值. \[ l{\rm Array}_0=1,\ \ \mu{\rm Array}_0=0,\ \ z{\rm Array}_0=0 \] \textbf{Step 4:} 对 $l{\rm Array},\mu{\rm Array},z{\rm Array}$ 数组更新. \[ {\rm for}\ k,\ l{\rm Array}_k=2(\bm{\vec{x}}_{k+1}-\bm{\vec{x}}_{k-1})-{\rm stepArray}_{k-1}\times\mu{\rm Array}_{k-1} \] \[ \mu{\rm Array}_k=\dfrac{{\rm stepArray}_k}{l{\rm Array}_k} \] \[ z{\rm Array}_k=\dfrac{\alpha{\rm Array}_{k}-{\rm stepArray}_{k-1}\times z{\rm Array}_{k-1}}{l{\rm Array}_k} \] \textbf{Step 5:} 再引入 $c{\rm Array}$ 数组并给尾索引赋值. \[ l{\rm Array}_{n+1}=1,\ \ z{\rm Array}_{n+1}=0,\ \ c{\rm Array}_{n+1}=0 \] \textbf{Step 6:} 再引入 $b{\rm Array},d{\rm Array}$ 数组并计算多项式各次项系数. \[ {\rm for}\ t=n,n-1,\ldots,0 \] \[ c{\rm Array}_{t}=z{\rm Array}_t-\mu{\rm Array}_t\times c{\rm Array}_{t+1} \] \[ b{\rm Array}_t=\dfrac{\bm{\vec{y}}_{t+1}-\bm{\vec{y}}_{t}}{{\rm stepArray}_t}-\dfrac{{\rm stepArray}_t(c{\rm Array}_{t+1}+2\times c{\rm Array}_t)}{3} \] \[ d{\rm Array}_t=\dfrac{c{\rm Array}_{t+1}-c{\rm Array}_t}{3\times {\rm stepArray}_t} \] \textbf{Step 7:} 最后打印 $\bm{\vec{y}},\ b{\rm Array},\ c{\rm Array},\ d{\rm Array}$. \section{\songti C 代码} \begin{lstlisting} /* System --> Linux & gcc8.1.0 File ----> NaturalCubicSpline.c Author --> Illusionna Create --> 2024/2/21 22:16:30 ''' -*- Encoding: UTF-8 -*- */ # include int main(){ printf("\033[H\033[J"); // ******************************************************** double X[] = {3, 4.5, 7, 9}; double Y[] = {2.5, 1, 2.5, 0.5}; // ******************************************************** int i, j; int lengthX = sizeof(X) / sizeof(X[0]); int lengthY = sizeof(Y) / sizeof(Y[0]); if (lengthX == lengthY){ int n = lengthX - 1; double stepArray[n], alphaArray[n], lArray[n+1], muArray[n+1], zArray[n+1], cArray[n+1], bArray[n], dArray[n]; // Step 1. for (i=0; i=0; --j){ cArray[j] = zArray[j] - muArray[j] * cArray[j+1]; bArray[j] = ((Y[j+1] - Y[j]) / stepArray[j]) - (stepArray[j] * (cArray[j+1] + 2 * cArray[j]) / 3); dArray[j] = (cArray[j+1] - cArray[j]) / (3 * stepArray[j]); } // Information. printf("The coefficients of each interval cubic polynomial:\n"); printf("%2s %8s %8s %8s %8s\n", "k", "ak", "bk", "ck", "dk"); for (i=0; i