《数值计算方法》课件

数值计算方法数值计算方法是解决复杂数学问题的重要工具，为科学研究和工程应用提供了强大的计算支持本课程将深入探讨数值计算的基础原理与实际应用，详细介绍计算机辅助科学计算的关键技术课程概述课程目标掌握数值计算的基本理论、算法及其在科学工程中的应用，培养解决实际计算问题的能力学习内容包括非线性方程求根、线性方程组、插值方法、数值积分、微分方程数值解等核心内容教学安排理论讲授与编程实践相结合，培养计算思维与实际解决问题的能力必备基础第一章绪论数值计算方法的本质用近似方法求解数学问题的计算技术数值计算方法的特点近似性、误差控制与算法稳定性发展历史从古代算盘到现代超级计算机误差分析基础理解与控制计算过程中的误差数值计算方法作为应用数学的重要分支，已成为解决现代科学工程问题不可或缺的工具随着计算机技术的飞速发展，数值方法的应用范围不断扩大，计算能力不断提高，为复杂问题的求解提供了有力支持数值计算方法的定义与应用基本定义主要应用领域数值计算方法是利用计算机求解无法获得解析解的数学问题的近•科学研究物理模拟、气象预报、天体运动似计算技术它通过将连续问题离散化，将无限过程有限化，实•工程设计结构分析、流体力学、热传导现对复杂数学模型的有效计算•信息技术图像处理、数据压缩、信号分析这些方法特别适用于那些没有解析表达式的问题，或虽有解析表•金融分析风险评估、投资组合优化达式但过于复杂难以实际应用的情况•生物医学药物设计、基因分析、医学成像数值计算的特点近似性数值计算的本质是近似而非精确，通过一系列有限步骤逼近真实解这种近似性使我们能够处理那些无法通过传统数学方法求解的问题误差控制误差在数值计算中不可避免，但可以通过科学的方法进行分析和控制良好的算法设计需要权衡计算精度与计算效率之间的关系算法稳定性稳定性是数值算法的关键特性，表示算法对输入数据微小变化的敏感程度高稳定性算法能够有效抑制误差累积和放大计算效率随着问题规模增大，计算量往往呈指数级增长高效算法设计能够充分利用计算机硬件性能，降低时间和空间复杂度误差分析基础截断误差舍入误差来源于数学模型的简化与近似计算机表示实数的有限精度导致•级数展开的截断•浮点数表示的限制•微分方程的离散化•运算过程中的数值舍入•无限过程的有限化•误差累积效应误差控制策略绝对误差与相对误差提高计算精度的方法衡量计算结果准确性的指标•选择合适的算法•绝对误差=|近似值-真实值|•优化计算步骤•相对误差=|绝对误差/真实值|•采用高精度计算•相对误差更具实际意义有效数字与相对误差数值示例有效数字位数相对误差限位

1.

7330.5×10⁻²位

1.

732150.5×10⁻⁴位

1.

732040.5×10⁻³位

0.

0017330.5×10⁻²位

173.

040.5×10⁻³有效数字是指从数值的第一个非零数字开始，一直到最后一个可靠数字为止的所有数字根据记数规则，位有效数字的相对误差限为n

0.5×10^1-n在实际计算中，有效数字的概念帮助我们判断计算结果的精确程度例如，当两个具有不同精度的数值进行运算时，结果的精度通常取决于精度较低的那个数值这在工程计算和科学研究中具有重要的实际意义第二章非线性方程求根方程求根概念求解的解fx=0x*二分法区间不断二分逼近简单迭代法构造不动点格式迭代法Newton利用切线快速逼近非线性方程的数值求根是数值计算的基本问题之一对于形如的方程，当是fx=0fx复杂的非线性函数时，通常难以获得解析解，必须借助数值方法求得近似解不同的求根方法有着各自的特点，在实际应用中需要根据问题特性选择合适的算法非线性方程举例典型例题工程应用实例求解方程在区间内的根非线性方程在工程领域有广泛应用x²=2sinx1,2通过变形可得fx=x²-2sinx=0在区间[1,2]内，有•结构工程确定材料受力平衡点•电路分析求解非线性电路的工作点•f1=1-2sin1≈1-2×

0.84≈-

0.680•化学反应平衡常数与反应速率计算•f2=4-2sin2≈4-2×

0.91≈

2.180•控制系统稳定性分析与控制参数确定根据零点存在定理，方程在区间内至少有一个根但无法1,2•流体力学临界流速与阻力系数求解通过初等函数表示其精确解，需要借助数值方法求解二分法基本原理基于零点存在定理，若连续函数在区间上满足，则fx[a,b]fa·fb0存在∈使通过不断二分区间并保留含根的子区间，最终c a,b fc=0逼近方程的根算法步骤找到初始区间，使

1.[a₀,b₀]fa₀·fb₀0计算中点，判断的符号

2.m=a+b/2fm若，则令；否则令

3.fa·fm0b=m a=m若小于给定精度或足够小，则停止；否则返回步骤

4.|b-a||fm|2收敛性分析每次迭代后区间长度减半，经过次迭代后，区间长度为n b₀-a₀/2ⁿ要达到精度，需要迭代次数，表现为线性收敛εn≥log₂b₀-a₀/ε简单迭代法构造迭代格式将方程转化为不动点形式fx=0x=φx检验收敛条件在根附近成立|φx|1执行迭代计算，直到满足终止条件xₙ₊₁=φxₙ简单迭代法的关键在于迭代格式的构造对于方程，可以将其变形为，其中是一个待定参数通过合理选择使得迭代fx=0x=x+λfxλλ函数在根附近满足，从而保证迭代序列的收敛性φx=x+λfx|φx|1当时（为方程的根），可以证明迭代误差满足，这表明简单迭代法是线性收敛的，收敛速度取|φx*|=q1x*|xₙ-x*|≤qⁿ/1-q·|x₁-x₀|决于导数的绝对值迭代法Newton几何意义法的几何意义是用函数在当前迭代点处的切线来逼近函数曲Newton fx xₙ线，切线与轴的交点作为下一次迭代点这种方法利用了函数的局部xxₙ₊₁线性特性，能在满足条件时快速逼近方程的根迭代公式推导对于方程，在点处的切线方程为fx=0xₙy=fxₙ+fxₙx-xₙ切线与轴交点处，解得x y=0xₙ₊₁=xₙ-fxₙ/fxₙ收敛特性当初始值足够接近根，且时，法表现为二次收x*fx*≠0Newton敛，即误差，其中为常数这意味着有效数字将以|eₙ₊₁|≤C|eₙ|²C倍数形式增加，收敛速度远快于线性收敛的方法牛顿迭代法改进弦截法（割线法）下山法多重根处理Newton弦截法用两点连线代替切线，避免了导数引入松弛因子控制迭代步长当在根处有阶零点时，标准λfx x*m计算法收敛变慢Newtonxₙ₊₁=xₙ-λ·fxₙ/fxₙ改进公式xₙ₊₁=xₙ-fxₙxₙ-xₙ₋₁/fxₙ-fxₙ₋₁xₙ₊₁=xₙ-m·fxₙ/fxₙ通过调整使，提高算法λ|fxₙ₊₁||fxₙ|收敛阶数约为，介于线性和二次收敛稳定性或使用代替进行迭代

1.618ux=fx/fx fx之间第三章线性代数方程组直接解法迭代解法特殊方程组病态问题消去法与分与三对角方程组可用追赶条件数较大的方程组对Gauss LUJacobi Gauss-解等方法通过有限步骤迭代通过逐步逼法高效求解，常见于边扰动敏感，需特殊处理Seidel直接求解方程组，适用近获得解，适用于大规界值问题离散化以保证计算精度于中小规模稠密矩阵模稀疏矩阵消去法Gauss消元过程通过初等行变换将系数矩阵转化为上三角形式，主要包括三个步骤消元、回代和计算解向量消元过程中，通过选取适当的主元可以提高计算稳定性主元选择为提高数值稳定性，通常采用主元策略•列主元每列选取绝对值最大元素作为主元计算复杂度•全主元在整个矩阵中选取绝对值最大元素对于n阶方程组，Gauss消去法的时间复杂度为On³，空间复杂度为合理的主元选择可有效避免舍入误差放大On²当n较大时，计算量迅速增长，需考虑并行计算或特殊矩阵结构优化分解LU基本思想分解算法分解将系数矩阵分解为一个下三角矩阵和一个上三角矩阵分解将对角线元素设为LU AL DoolittleL1的乘积求解转化为两步先求解得到U A=LU Ax=b Ly=b，再求解得到y Ux=y xfork=1to nfor i=k ton这种方法的优势在于分解只需进行一次，当右端项变化时，只bUk,i=Ak,i-ΣLk,jUj,i需重新进行前代和回代运算，而无需重新分解矩阵，非常适合Aj=1to k-1求解具有多个右端项的方程组fori=k+1to nLi,k=[Ai,k-ΣLi,jUj,k]/Uk,kj=1to k-1分解将对角线元素设为，计算过程类似Crout U1病态问题与数值稳定性病态问题定义条件数当线性方程组对输入数据的微小条件数是衡量κA=||A||·||A⁻¹||变化极为敏感时，称该问题为病矩阵病态程度的重要指标A态问题这类问题在数值计算中越大，表明方程组越敏感于κA会导致结果的显著误差，即使计扰动当≫时，问题为病κA1算过程中的舍入误差很小态；当接近时，问题为良κA1态病态问题处理处理病态问题的常用技术包括预处理、正则化方法、高精度计算以及特殊的数值算法在实际应用中，识别并正确处理病态问题对保证计算结果的可靠性至关重要在实际应用中，法则虽然在理论上可行，但由于需要计算行列式，计算量Cramer为，且易受舍入误差影响，几乎不用于实际数值计算对于病态方程组，直接On!法可能会导致严重的精度损失，此时应考虑使用迭代法或其他专门设计的算法迭代法求解线性方程组迭代迭代Jacobi Gauss-Seidel将矩阵分解为，其中为对角矩阵，为严格下三角改进迭代，使用已更新的分量A A=D-L-U D-L Jacobi部分，为严格上三角部分迭代格式为-Ux⁽ᵏ⁺¹⁾=D-L⁻¹Ux⁽ᵏ⁾+D-L⁻¹bx⁽ᵏ⁺¹⁾=D⁻¹L+Ux⁽ᵏ⁾+D⁻¹b计算第个分量时i计算第个分量时使用上一轮迭代的所有分量ix_i⁽ᵏ⁺¹⁾=b_i-Σa_ij x_j⁽ᵏ⁺¹⁾-Σa_ij x_j⁽ᵏ⁾/a_iix_i⁽ᵏ⁺¹⁾=b_i-Σa_ij x_j⁽ᵏ⁾/a_ii一般来说，迭代收敛速度快于迭代Gauss-Seidel Jacobi迭代法的收敛条件通常要求谱半径，其中为迭代矩阵对于严格对角占优矩阵，两种迭代法均收敛实际应用中，可通过ρG1G方法引入松弛因子加速收敛，特别适用于大型稀疏方程组求解SORSuccessive Over-Relaxationω第四章插值方法插值基本概念插值Lagrange基于已知离散数据点构造连续函数的方利用基函数构造多项式，每个基函数在法，函数曲线必须通过所有已知数据点对应节点处为，在其他节点处为10样条插值插值Newton分段低次插值，避免高次多项式的龙格基于差商构造，便于递增数据点，计算现象，保持光滑连续性效率高插值Lagrange插值多项式构造误差分析给定个数据点，插值多如果被插函数在区间上有阶连续导数，则插值误差n+1x₀,y₀,x₁,y₁,...,xₙ,yₙLagrange fx[a,b]n+1项式为为L_nx=Σy_iℓ_ix R_nx=fx-L_nx=f^n+1ξ/n+1!·Πx-x_i其中为基函数其中∈，且依赖于ℓ_ix Lagrangeξ[a,b]x误差大小受节点分布影响，等距节点在区间端点附近可能出现龙ℓ_ix=Πx-x_j/x_i-x_j,j≠i格现象，导致误差急剧增大基函数满足当时，否则为ℓ_ix_j=1i=j0插值Newton差商与差分插值多项式Newton一阶差商f[x₀,x₁]=fx₁-N_nx=fx₀+f[x₀,x₁]x-x₀fx₀/x₁-x₀+f[x₀,x₁,x₂]x-x₀x-x₁+...+f[x₀,...,xₙ]x-x₀...x-xₙ₋₁二阶差商f[x₀,x₁,x₂]=f[x₁,x₂]-f[x₀,x₁]/x₂-x₀与Lagrange插值等价，但便于递增数据点更高阶差商依此类推，可通过差商表计算前向与后向差分等距节点时，可用前向差分或后向差分∇表示Δⁱf₀ⁱfₙ前向公式适合在区间左端插值，后向公式适合在右端插值Newton插值法的主要优势在于添加新节点时，可以利用已有计算结果，只需计算Newton涉及新节点的差商，提高了计算效率在实际应用中，当数据点较多时，通常不选择高次多项式插值，而是采用分段低次插值方法，如三次样条插值三次样条插值样条函数定义1在每个子区间上采用三次多项式，保证在节点处具有二阶连续导数三次样条条件2函数值匹配、一阶导数连续、二阶导数连续边界条件类型自然边界、固支边界、周期边界等优势特点4避免高次多项式的龙格现象，保持曲线光滑性三次样条插值的基本思想是在每个子区间[xᵢ,xᵢ₊₁]上构造三次多项式S_ix，使整体样条函数Sx满足

1.Sxᵢ=fxᵢ，i=0,1,...,n（插值条件）

2.S_ixᵢ₊₁=S_{i+1}xᵢ₊₁，i=0,1,...,n-2（函数连续）

3.S_ixᵢ₊₁=S_{i+1}xᵢ₊₁，i=0,1,...,n-2（一阶导数连续）

4.S_ixᵢ₊₁=S_{i+1}xᵢ₊₁，i=0,1,...,n-2（二阶导数连续）第五章数值积分数值求积基本思想公式复化求积公式积分Newton-Cotes Romberg用简单函数近似被积函数基于多项式插值的求积方法区间细分提高精度利用外推加速收敛数值积分旨在求解定积分的近似值，特别适用于被积函数没有原函数表达式或原函数表达式过于复杂的情况不同的数值积∫[a,b]fxdx分方法有各自的精度特点和适用范围，选择合适的方法对提高计算效率和精度至关重要求积公式Newton-Cotes矩形法则用常数函数近似被积函数，即零次多项式插值I≈b-a·fa+b/2中点矩形法代数精度为1，即对一次多项式积分精确梯形法则用一次多项式（直线）近似被积函数I≈b-a/2·[fa+fb]代数精度为1，即对一次多项式积分精确辛普森法则用二次多项式近似被积函数I≈b-a/6·[fa+4fa+b/2+fb]代数精度为3，即对三次多项式积分精确梯形法则与辛普森法则梯形法则辛普森法则梯形法则是二点公式，相当于用线性函数近似辛普森法则是三点公式，相当于用二次多项式Newton-Cotes Newton-Cotes被积函数其公式为近似被积函数其公式为∫[a,b]fxdx≈b-a/2·[fa+fb]∫[a,b]fxdx≈b-a/6·[fa+4fa+b/2+fb]当有二阶连续导数时，截断误差为当有四阶连续导数时，截断误差为fx fx，∈，∈E_T=-b-a³/12·fξξa,b E_S=-b-a⁵/2880·f⁽⁴⁾ξξa,b这表明梯形法则对线性函数积分是精确的，误差与积分区间长度辛普森法则对三次多项式积分是精确的，误差与积分区间长度的的三次方成正比五次方成正比，因此精度显著高于梯形法则复化求积公式区间划分思想复化梯形公式复化求积公式的核心思想是将积将区间等分为份，步长[a,b]n分区间均匀划分为个子区，复化梯形公式为[a,b]n h=b-a/n间，在每个子区间上应用基本求T_n=h/2·[fa+fb+2·Σ积公式，然后将结果相加这种，fa+ih]i=1,2,...,n-1方法可以有效提高数值积分的精截断误差度，特别是当被积函数在某些区E_T=-b-域变化剧烈时a·h²/12·fξ复化辛普森公式将区间等分为份，步长，复化辛普森公式为[a,b]2n h=b-a/2nS_n=h/3·[fa+fb+4·Σfa+2i-1h+2·Σfa+2ih]截断误差E_S=-b-a·h⁴/180·f⁽⁴⁾ξ求积法Romberg1基本原理求积法基于复化梯形公式和外推技术，通过数列加速Romberg Richardson收敛方法消除低阶误差项，显著提高计算精度该方法计算效率高，收敛速度快，是实际应用中常用的高精度数值积分方法计算步骤计算初始梯形公式，步长为

1.T0,0h=b-a逐步减半步长，计算，

2.Tk,0k=1,2,...,m利用外推公式计算高阶近似

3.，Tk,j=[4^j·Tk,j-1-Tk-1,j-1]/4^j-1j=1,2,...,k最终结果即为高精度积分近似值

4.Tm,m误差分析求积法的精度随着计算层数的增加而显著提高第层的Romberg mTm,m包含的最低阶误差项为Oh²ᵐ⁺²这意味着即使使用相对较少的函数求值，也能获得高精度的积分结果第六章常微分方程数值解数值稳定性分析单步法与多步法数值方法的稳定性是指算法对初始条件和舍入初值问题定义单步法仅使用当前点信息计算下一点近似值，误差的敏感程度绝对稳定性关注特定步长下常微分方程初值问题是求解形如y=fx,y，如欧拉法和Runge-Kutta法；多步法利用多个的误差增长，相对稳定性关注数值解对精确解yx₀=y₀的方程对于大多数非线性微分方已知点信息，如Adams法单步法易于启动但的逼近程度刚性问题需要特殊的隐式方法以程，难以获得解析解，因此数值方法成为求解精度有限，多步法精度高但需特殊启动步骤保证计算稳定性这类问题的重要手段数值解的基本思想是将数值方法的选择需平衡精度、稳定性和效率连续问题离散化，通过逐步推进计算近似解常微分方程初值问题数学模型与定义数值方法分类常微分方程初值问题的标准形式为显式方法直接计算下一步近似值y=fx,y,yx₀=y₀•显式欧拉法（前向欧拉法）•显式Runge-Kutta方法或高阶方程方法•Adams-Bashforthy⁽ⁿ⁾=fx,y,y,...,y⁽ⁿ⁻¹⁾,yx₀=y₀,yx₀=y₁,...,y⁽ⁿ⁻¹⁾x₀隐式方法通过解方程获得下一步值=yₙ₋₁高阶方程可通过引入新变量转化为一阶方程组当函数满足•隐式欧拉法（后向欧拉法）fLipschitz条件时，初值问题存在唯一解•梯形法（Crank-Nicolson方法）方法•Adams-Moulton欧拉方法显式欧拉法显式欧拉法（前向欧拉法）是最简单的数值方法，通过切线近似求解y_{n+1}=y_n+h·fx_n,y_n其中h为步长该方法计算简单，但精度较低，局部截断误差为Oh²，全局截断误差为Oh隐式欧拉法隐式欧拉法（后向欧拉法）使用下一步点的导数值y_{n+1}=y_n+h·fx_{n+1},y_{n+1}这是一个隐式方程，通常需要通过迭代方法求解隐式欧拉法具有良好的稳定性，适用于刚性问题改进欧拉法改进欧拉法（修正欧拉法）结合预测和校正步骤预测ỹ_{n+1}=y_n+h·fx_n,y_n校正y_{n+1}=y_n+h/2·[fx_n,y_n+fx_{n+1},ỹ_{n+1}]这实际上是二阶Runge-Kutta方法，局部截断误差为Oh³方法Runge-Kutta基本原理通过多阶段计算提高精度，匹配泰勒展开的高阶项四阶Runge-Kutta公式最常用的RK4方法，平衡精度与计算量步长控制策略自适应步长根据局部误差估计动态调整四阶Runge-Kutta方法（RK4）是实际应用中最常用的单步法，其公式为k₁=fxₙ,yₙk₂=fxₙ+h/2,yₙ+h·k₁/2k₃=fxₙ+h/2,yₙ+h·k₂/2k₄=fxₙ+h,yₙ+h·k₃yₙ₊₁=yₙ+h/6·k₁+2k₂+2k₃+k₄RK4方法的局部截断误差为Oh⁵，全局截断误差为Oh⁴，计算精度高且稳定性好，适用于大多数非刚性问题多步法方法方法Adams-Bashforth Adams-Moulton方法是常用的显式多步法，通过插值多项式方法是隐式多步法，使用包括点在内的历Adams-Bashforth Adams-Moulton n+1近似积分函数步公式利用个历史点计算史点p Adams-Bashforth p下一点的值y_{n+1}=y_n+h·[b_{-1}·fx_{n+1},y_{n+1}+Σy_{n+1}=y_n+h·Σb_j·fx_{n-j},y_{n-j}b_j·fx_{n-j},y_{n-j}]常用的二步公式为常用的二步公式为y_{n+1}=y_n+h/2·3fx_n,y_n-fx_{n-1},y_{n-1}y_{n+1}=y_n+h/12·5fx_{n+1},y_{n+1}+8fx_n,y_n-fx_{n-1},y_{n-1}优点是计算效率高，但稳定区域较小隐式方法稳定性更好，但需要迭代求解方程在实际应用中，通常采用预测校正方法，即先用方法预测的值，再用方法校正这种-Adams-Bashforth y_{n+1}Adams-Moulton方法平衡了计算效率与精度，是求解非刚性常微分方程的有效方法对于刚性方程，则需要使用专门的刚性求解器，如法（后向BDF差分公式）第七章偏微分方程数值解有限差分法抛物型方程用差分代替偏导数，将连续问题离散化如热传导方程，描述扩散过程•显式与隐式格式•显式与隐式差分格式•稳定性与收敛性分析•Crank-Nicolson格式•网格剖分与边界处理•von Neumann稳定性分析椭圆型方程双曲型方程如方程，描述平衡状态如波动方程，描述振动与传播Poisson五点差分格式4中心差分格式••迭代解法条件••CFL•快速求解技术•特征线方法有限差分法差分近似基础有限差分法的核心是用差分代替偏导数常用的差分近似包括前向差分∂u/∂x≈ux+h,y-ux,y/h+Oh差分格式构造后向差分∂u/∂x≈ux,y-ux-h,y/h+Oh将偏微分方程中的各阶偏导数用差分近似代替，得到差分方程根据选择中心差分∂u/∂x≈ux+h,y-ux-h,y/2h+Oh²不同的时间层，可构造显式格式（仅使用已知时间层的值）或隐式格式二阶导数∂²u/∂x²≈ux+h,y-2ux,y+ux-h,y/h²+Oh²（包含未知时间层的值）稳定性分析3数值解的稳定性是指计算误差是否随时间增长而放大常用vonNeumann方法和矩阵方法分析稳定性CFL条件是许多显式格式的必要稳定条件抛物型方程数值解一维热传导方程一维热传导方程是典型的抛物型方程∂u/∂t=α·∂²u/∂x²，描述热量在介质中的扩散过程在数值求解中，需要设定初始条件（初始温度分布）和边界条件（边界上的温度或热流）显式差分格式前向时间、中心空间格式（FTCS）u_i^{j+1}-u_i^j/Δt=α·u_{i+1}^j-2u_i^j+u_{i-1}^j/Δx²计算简单，但有条件稳定，要求r=α·Δt/Δx²≤1/2隐式差分格式后向时间、中心空间格式（BTCS）u_i^{j+1}-u_i^j/Δt=α·u_{i+1}^{j+1}-2u_i^{j+1}+u_{i-1}^{j+1}/Δx²需要求解三对角线性方程组，但无条件稳定Crank-Nicolson格式结合显式和隐式格式的优点u_i^{j+1}-u_i^j/Δt=α/2·[u_{i+1}^j-2u_i^j+u_{i-1}^j+u_{i+1}^{j+1}-2u_i^{j+1}+u_{i-1}^{j+1}]/Δx²二阶精度（时间和空间），无条件稳定椭圆型方程数值解方程离散化迭代求解方法Poisson二维方程是典型的椭圆迭代Poisson∂²u/∂x²+∂²u/∂y²=fx,y Jacobi型方程，描述平衡状态下的场分布，如静电场、温度场等u_{i,j}^{k+1}=u_{i+1,j}^k+u_{i-1,j}^k+u_{i,j+1}^k+采用中心差分近似u_{i,j-1}^k-h²·f_{i,j}/4迭代利用最新计算的值u_{i+1,j}-2u_{i,j}+u_{i-1,j}/Δx²+u_{i,j+1}-2u_{i,j}Gauss-Seidel+u_{i,j-1}/Δy²=f_{i,j}加速引入松弛因子SORω当时，简化为五点差分格式Δx=Δy=hu_{i,j}^{k+1}=1-ω·u_{i,j}^k+ω/4·u_{i+1,j}^k+u_{i-u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}-4u_{i,j}/h²=1,j}^{k+1}+u_{i,j+1}^k+u_{i,j-1}^{k+1}-h²·f_{i,j}f_{i,j}最优松弛因子可显著提高收敛速度第八章最优化方法最优化问题寻找目标函数的极值点一维搜索方法黄金分割法、斐波那契法和抛物线法多维无约束优化梯度法、共轭梯度法与拟牛顿法约束优化问题惩罚函数法与拉格朗日乘子法最优化方法在科学研究和工程应用中具有广泛的应用，如参数估计、机器学习、信号处理和控制系统设计等数值优化算法的选择需要考虑目标函数的特性、问题规模以及收敛速度和计算效率的平衡一维搜索方法黄金分割法斐波那契法抛物线插值法黄金分割法是一种有效的一维搜索方法，利用黄斐波那契法预先确定迭代次数n，利用斐波那契抛物线插值法利用三点构造二次多项式近似目标金分割比τ=√5-1/2≈

0.618将区间划分每次数列Fₙ划分区间相比黄金分割法，斐波那契法函数，然后求出抛物线的极小点作为新的试探迭代只需计算一个新的函数值，区间长度以固定在最后几步可以更快地缩小区间，但需要预先知点该方法适用于光滑函数，收敛速度通常快于比例缩小道迭代次数前两种方法算法步骤每次迭代后区间长度比为Fₙ₋ₖ₋₁/Fₙ₋ₖ₊₁，随着k增当目标函数接近二次函数时，抛物线法效果最加逐渐接近黄金分割比佳，但对于有多个极值点的函数可能会出现收敛•初始区间[a,b]，计算点x₁=a+1-τb-a和问题x₂=a+τb-a•比较fx₁和fx₂的大小，保留含极小值的子区间•重复过程直到区间长度小于给定精度梯度下降法基本原理与几何解释梯度下降法是最基本的多维优化算法，基于目标函数的负梯度方向是函数值下降最快的方向这一事实在每次迭代中，沿负梯度方向移动一定步长，逐步逼近局部极小点对于目标函数fx，迭代公式为x⁽ᵏ⁺¹⁾=x⁽ᵏ⁾-αₖ∇fx⁽ᵏ⁾其中αₖ是步长参数，∇fx⁽ᵏ⁾是函数在点x⁽ᵏ⁾处的梯度步长选择策略步长αₖ的选择对算法性能有重要影响•固定步长简单但可能导致收敛问题•精确线搜索找到使fx⁽ᵏ⁾-α∇fx⁽ᵏ⁾最小的α值•非精确线搜索满足一定条件（如Armijo条件）的步长•自适应步长根据历史迭代信息动态调整收敛特性与应用限制梯度下降法对于凸函数保证收敛到全局最小值，对于非凸函数可能收敛到局部最小值当目标函数条件数较大（即Hessian矩阵特征值分布不均匀）时，算法可能呈现之字形路径，收敛缓慢在机器学习等领域，随机梯度下降法（SGD）是处理大规模数据的重要变种共轭梯度法1共轭方向概念两个向量d⁽ⁱ⁾和d⁽ʲ⁾关于正定矩阵A的共轭，满足d⁽ⁱ⁾ᵀAd⁽ʲ⁾=0，i≠j共轭梯度法构造一组共轭方向，使得沿每个方向的一维优化不会破坏之前方向上已达到的最优性对于n维二次函数，共轭梯度法理论上可在n步内收敛到精确解算法实现共轭梯度法的迭代过程

1.初始点x⁽⁰⁾，计算初始负梯度d⁽⁰⁾=-∇fx⁽⁰⁾

2.沿方向d⁽ᵏ⁾进行一维搜索，找到最优步长αₖ

3.更新x⁽ᵏ⁺¹⁾=x⁽ᵏ⁾+αₖd⁽ᵏ⁾

4.计算新梯度g⁽ᵏ⁺¹⁾=∇fx⁽ᵏ⁺¹⁾

5.计算βₖ₊₁=g⁽ᵏ⁺¹⁾ᵀg⁽ᵏ⁺¹⁾/g⁽ᵏ⁾ᵀg⁽ᵏ⁾Fletcher-Reeves公式

6.更新方向d⁽ᵏ⁺¹⁾=-g⁽ᵏ⁺¹⁾+βₖ₊₁d⁽ᵏ⁾预处理技术对于条件数较大的问题，可引入预处理矩阵M来改善收敛性能预处理共轭梯度法解决的是M⁻¹Ax=M⁻¹b而非直接解Ax=b好的预处理矩阵M应接近A但更易求逆，常用如对角预处理、不完全LU分解等第九章特征值计算矩阵特征值计算是数值计算中的重要问题，在振动分析、结构稳定性、量子力学、主成分分析等领域有广泛应用不同的算法适用于不同类型的矩阵和计算需求幂法简单高效但只能求最大特征值；算法可计算全部特征值但计算量大；法适用于对称矩QR Jacobi阵；而和方法则专为大型稀疏矩阵设计Lanczos Arnoldi幂法与反幂法幂法原理反幂法原理位移技术收敛分析幂法是计算矩阵最大模特反幂法用于计算矩阵最小通过引入位移，可以计幂法的收敛速度取决于最μ征值及其对应特征向量的模特征值，基本思路是对算接近的特征值位移大两个特征值模的比值μ简单迭代方法基本思想矩阵求逆后应用幂法实反幂法可以有效计算预先当这个比值接|λ₂/λ₁|是反复用矩阵乘以向际实现中，通常通过求解估计位置附近的特征值，近时，收敛会很慢，需1量，向量将逐渐指向最大线性方程组来是求解特定特征值的有效要加速技术如加A-μIy=x Aitken特征值对应的特征向量方避免显式计算矩阵逆方法速或商迭代Rayleigh向算法QR分解基础基本算法QR QR分解是将矩阵分解为一个正交矩阵和一个上三角矩阵的乘基本算法的迭代步骤为QR AQ RQR积分解可以通过正交化、A=QR QRGram-Schmidt计算分解

1.QR Aₖ=QₖRₖ变换或旋转等方法实现Householder Givens计算下一轮迭代矩阵

2.Aₖ₊₁=RₖQₖ=Qₖ⁻¹AₖQₖ在特征值计算中，分解是算法的核心操作，每次迭代都需要QR QR进行一次分解QR迭代过程中，矩阵逐渐接近上三角（或对角块）形式，其对角Aₖ元素收敛到矩阵的特征值A实际应用中，为提高算法效率，通常先将矩阵化为形式（上矩阵只有主对角线和主对角线上方以及紧邻主对角Hessenberg Hessenberg线下方的元素非零），然后再应用算法此外，引入位移技术可以大幅加速收敛QR选择位移量（通常为当前矩阵右下角子矩阵的特征值近似）

1.μₖ计算分解

2.QR Aₖ-μₖI=QₖRₖ更新

3.Aₖ₊₁=RₖQₖ+μₖI第十章曲线拟合与逼近最小二乘原理线性拟合1通过最小化残差平方和寻找最佳拟合参使用线性参数模型拟合数据，易于计算数正交多项式4多项式拟合3利用特殊多项式提高数值稳定性采用多项式函数逼近数据点，灵活性高曲线拟合与逼近是数据分析与建模的基础工具，广泛应用于实验数据处理、模式识别、信号分析等领域拟合方法的选择应根据数据特性、精度要求和计算效率综合考虑过度拟合（使用过高阶模型）可能导致在数据点间吻合度高但预测能力差的结果线性最小二乘拟合问题描述与原理正规方程给定个数据点，线性最小二乘拟合求解最小二乘问题可以通过正规方程m x₁,y₁,x₂,y₂,...,xₘ,yₘ寻找线性模型的参数，使fx=a₁φ₁x+a₂φ₂x+...+aₙφₙx aⱼAᵀAa=Aᵀy残差平方和最小其中是矩阵，，是待求参数向量，是观测值A m×n Aᵢⱼ=φⱼxᵢa yminΣ[yᵢ-fxᵢ]²向量这里的线性是指模型对参数是线性的，基函数可以是aⱼφⱼx正规方程的解为a=AᵀA⁻¹Aᵀy非线性函数，如多项式、三角函数等当数据点数量远大于参数数量时，这种方法可以有效平滑数m n据中的噪声在实际计算中，直接求解正规方程可能导致数值不稳定，特别是当基函数接近线性相关时更稳健的方法是使用分解或奇异值分解QR方法尤其适合处理秩亏损或接近秩亏损的问题，可以有效避免条件数较大引起的数值不稳定性SVD SVD正交多项式近似Chebyshev多项式Legendre多项式正交多项式的优势Chebyshev多项式是定义在区间[-1,1]上的Legendre多项式Pₙx是另一类重要的正使用正交多项式进行函数逼近具有明显优势正交多项式系，第一类Chebyshev多项式交多项式，在区间[-1,1]上关于权函数计算系数简单，可以递增阶数而不需重新计Tₙx满足Tₙcosθ=cosnθ这类多wx=1正交Legendre多项式常用于求解算所有系数，且数值稳定性好由于正交性，项式在逼近理论中具有重要地位，特别是在微分方程和物理问题，特别是在球坐标系中最小二乘拟合的系数矩阵为对角矩阵，避免均匀逼近中，Chebyshev多项式可以最小的问题了求解线性方程组的复杂性化最大误差在实际应用中，Chebyshev多项式特别适合函数逼近和数值积分当使用Chebyshev点（即x_j=cos2j-1π/2n，j=1,2,...,n）作为插值节点时，可以最大程度地减小Runge现象，获得接近最佳均匀逼近的结果基于Chebyshev多项式的函数逼近在计算科学中有广泛应用，如数值微分、积分和微分方程求解等第十一章方法Monte Carlo随机数生成Monte Carlo方法的基础是高质量的随机数生成计算机通常使用伪随机数生成器PRNG产生具有统计随机性的数列常用的PRNG包括线性同余法、梅森旋转算法等生成的随机数应满足均匀性、独立性和长周期等特性Monte Carlo积分Monte Carlo积分是一种基于概率统计的数值积分方法，特别适合高维积分问题基本思想是将积分问题转化为期望计算，通过随机抽样估计积分值Monte Carlo积分的收敛速度与维数无关，是处理高维问题的有力工具随机模拟与抽样Monte Carlo方法广泛应用于物理系统模拟、金融风险分析、分子动力学等领域通过大量随机试验模拟复杂系统的行为，获得统计特性重要性抽样、马尔可夫链MonteCarloMCMC等高级技术可以提高抽样效率和准确性积分Monte Carlo基本原理Monte Carlo积分的基本思想是将定积分∫[a,b]fxdx表示为期望形式b-aE[fX]，其中X是区间[a,b]上的均匀随机变量通过生成n个随机样本点x₁,x₂,...,xₙ并计算样本均值，可以估计积分值I≈b-a/n·Σfxᵢ这种方法的标准误差与1/√n成正比，与维数无关，这是其在高维积分中优于传统数值积分方法的关键方差减少技术为提高Monte Carlo积分的效率，发展了多种方差减少技术•分层抽样将积分区域划分为子区域，在每个子区域中抽样•控制变量法利用与被积函数相关且易于积分的函数减小方差•对偶变量法使用负相关的随机变量对减小方差•重要性抽样根据被积函数的特性调整抽样分布高维积分应用Monte Carlo积分在高维积分问题中具有显著优势，广泛应用于•量子力学计算多体系统的能量与波函数•金融数学期权定价与风险评估•统计物理多粒子系统的热力学性质•计算机图形学全局光照渲染实际应用案例工程设计科学计算人工智能在桥梁、建筑和航空航天等工程领域，数数值天气预报是数值计算在科学领域的典现代人工智能和机器学习严重依赖数值计值计算方法广泛应用于结构分析和流体动型应用，涉及求解复杂的流体动力学方程算深度学习中的反向传播算法本质上是力学模拟有限元分析可以预测复杂结构组大气模型通过数值方法模拟大气运动求解大规模优化问题，需要高效的数值方在各种载荷下的应力分布和变形情况，帮和物理过程，预测未来天气变化气象部法最优化算法如随机梯度下降、Adam助工程师优化设计，提高安全性和经济门使用这些模型提供天气预报和气候预等是训练神经网络的核心，推动了计算机性测，为防灾减灾提供科学依据视觉、自然语言处理等领域的革命性进展总结与展望。