西交计算方法总结

西南交⼤数值计算1.秦九韶算法利⽤秦九韶算法简化求多项式1110n n n n x a x a y x a a --=++++ 的值的运算式，并写程序计算多项式42352x y x x =--+在1x =-点处的值。

1.2秦九韶算法简化多项式计算多项式1110n n n n x a x a y x a a --=++++ 的值：1.直接计算i i x a ，逐项相加，共需要加法和乘法的次数为n 次、2)1(+n n 次； 2.⽤秦九韶算法简化，则y=(…0121)...))(a x a x a x a x a n n n +++++--，从内到外逐步计算⼀次多项式的值，共需要加法和乘法的次数各为n 次。

2.⽜顿法及基于⽜顿算法下的Steffensen 加速法分别⽤⽜顿法，及基于⽜顿算法下的Steffensen 加速法(1) 求ln(x +sin x )=0的根。

初值x0分别取0.1, 1,1.5, 2, 4进⾏计算。

(2) 求sin x =0的根。

初值x0分别取1，1.4，1.6, 1.8，3进⾏计算。

分析其中遇到的现象与问题。

2.1 问题分析⽜顿法是⼀种迭代法，是求⽅程根的重要⽅法之⼀，通过使⽤函数f(x)在近似根0x 附近的⼀阶泰勒多项式近似表⽰来寻找⽅程的根，在⽅程f(x) = 0的单根附近具有平⽅收敛。

其迭代公式为：)()(1k k k k x f x f x x '-=+ Steffensen 加速法公式：)()()(x f x f x x '-=? )(n n x y ?= )(n n y z ?=nn n n n n n x y z x y x x +---=+2)(212.2求ln(x+sinx)=0的根 2.2.1⽜顿法kk k k k k k x x x x x x x sin cos 1)sin ln(1+++-=+2.2.2 Steffensen 加速法 2.2.3 结果及分析初值⽜顿法结果（循环次数） Steffensen 加速法结果（循环次数）0.1 0.5109734294（7） -2.118746196 0.2 0.5109734294（6） 0.5109734294（5） 0.5 0.5109734294（4）0.5109734294（3） 1 0.5109734294（6）0.5109734294（5）1.5 溢出 1.5 2 溢出 2 4溢出4（误差限为20-e ）2.3求sinx=0的根 2.3.1 ⽜顿法kkk k x x x x cos sin 1-=+ 2.3.2 Steffensen 加速法 2.3.3 结果及分析初值⽜顿法结果（循环次数） Steffensen 加速法结果（循环次数）1 溢出 01.43.1415926535898（7） -3.141592651（4）1.6 31.4159265358965（8） 25.13274123（6） 1.8 6.28318530141765（4） 6.283185307（3） 33.14159265330048（3） 3.141592654（3）3.数值积分（1）实际验证梯形求积公式、Simpson 求积公式、Newton-Cotes 求积公式的代数精度。

《计算机算法设计与分析》上机实验报告姓名：班级：学号：日期：2016年12月23日算法实现题3-14 最少费用购物问题★问题描述：商店中每种商品都有标价。

例如，一朵花的价格是2元，一个花瓶的价格是5元。

为了吸引顾客，商店提供了一组优惠商品价。

优惠商品是把一种或多种商品分成一组，并降价销售。

例如，3朵花的价格不是6元而是5元。

2个花瓶加1朵花的优惠价格是10元。

试设计一个算法，计算出某一顾客所购商品应付的最少费用。

★算法设计：对于给定欲购商品的价格和数量，以及优惠价格，计算所购商品应付的最少费用。

★数据输入：由文件input.txt提供欲购商品数据。

文件的第1行中有1个整数B（0≤B≤5），表示所购商品种类数。

在接下来的B行中，每行有3个数C,K和P。

C表示商品的编码（每种商品有唯一编码），1≤C≤999；K表示购买该种商品总数，1≤K≤5；P是该种商品的正常单价（每件商品的价格），1≤P≤999。

请注意，一次最多可购买5*5=25件商品。

由文件offer.txt提供优惠商品价数据。

文件的第1行中有1个整数S（0≤S≤99），表示共有S种优惠商品组合。

接下来的S行，每行的第1个数描述优惠商品组合中商品的种类数j。

接着是j个数字对（C，K），其中C是商品编码，1≤C≤999；K表示该种商品在此组合中的数量，1≤K≤5。

每行最后一个数字P （1≤P≤9999）表示此商品组合的优惠价。

★结果输出：将计算出的所购商品应付的最少费用输出到文件output.txt。

输入文件示例输出文件示例Input.txt offer.txt output.txt2 2 147 3 2 1 7 3 58 2 5 2 7 1 8 2 10解：设cost（a，b，c，d，e）表示购买商品组合（a，b，c，d，e）需要的最少费用。

A[k]，B[k]，C[k]，D[k]，E[k]表示第k种优惠方案的商品组合。

offer （m）是第m种优惠方案的价格。

《线性代数》复习提纲第一部分：基本要求（计算方面）四阶行列式的计算；N阶特殊行列式的计算（如有行和、列和相等）；矩阵的运算（包括加、减、数乘、乘法、转置、逆等的混合运算）；求矩阵的秩、逆（两种方法）；解矩阵方程；含参数的线性方程组解的情况的讨论；齐次、非齐次线性方程组的求解（包括唯一、无穷多解）；讨论一个向量能否用和向量组线性表示；讨论或证明向量组的相关性；求向量组的极大无关组，并将多余向量用极大无关组线性表示；将无关组正交化、单位化；求方阵的特征值和特征向量；讨论方阵能否对角化，如能，要能写出相似变换的矩阵及对角阵；通过正交相似变换（正交矩阵）将对称矩阵对角化；写出二次型的矩阵，并将二次型标准化，写出变换矩阵；判定二次型或对称矩阵的正定性。

第二部分：基本知识一、行列式1．行列式的定义用n^2个元素aij组成的记号称为n阶行列式。

（1）它表示所有可能的取自不同行不同列的n个元素乘积的代数和；（2）展开式共有n!项，其中符号正负各半；2．行列式的计算一阶|α|=α行列式，二、三阶行列式有对角线法则；N阶（n>=3）行列式的计算：降阶法定理：n阶行列式的值等于它的任意一行（列）的各元素与其对应的代数余子式乘积的和。

方法：选取比较简单的一行（列），保保留一个非零元素，其余元素化为0，利用定理展开降阶。

特殊情况上、下三角形行列式、对角形行列式的值等于主对角线上元素的乘积；（2）行列式值为0的几种情况：Ⅰ行列式某行（列）元素全为0；Ⅱ行列式某行（列）的对应元素相同；Ⅲ行列式某行（列）的元素对应成比例；Ⅳ奇数阶的反对称行列式。

二．矩阵1．矩阵的基本概念（表示符号、一些特殊矩阵――如单位矩阵、对角、对称矩阵等）；2．矩阵的运算（1）加减、数乘、乘法运算的条件、结果；（2）关于乘法的几个结论：①矩阵乘法一般不满足交换律（若AB＝BA，称A、B是可交换矩阵）；②矩阵乘法一般不满足消去律、零因式不存在；③若A、B为同阶方阵，则|AB|=|A|*|B|；④|kA|=k^n|A|3．矩阵的秩（1）定义非零子式的最大阶数称为矩阵的秩；（2）秩的求法一般不用定义求，而用下面结论：矩阵的初等变换不改变矩阵的秩；阶梯形矩阵的秩等于非零行的个数（每行的第一个非零元所在列，从此元开始往下全为0的矩阵称为行阶梯阵）。

第一章绪论1.1数值计算现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。

通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。

一、本课程的任务：寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学（算术）的方法求解——了解计算的基础方法，基本结构（否则只须知道数值软件）——并研究其性质。

立足点：面向数学——解决数学问题面向计算机——利用计算机作为工具充分发挥计算机的功能，设计算法，解决数学问题例如：迭代法、并行算法二、问题的类型1、离散问题：例如，求解线性方程组bAx=——从离散数据：矩阵A和向量b，求解离散数据x；2、连续问题的离散化处理：例如，数值积分、数值微分、微分方程数值解；3、离散问题的连续化处理：例如，数据近似，统计分析计算；1.2数值方法的分析在本章中我们不具体讨论算法，首先讨论算法分析的基础——误差。

一般来讲，误差主要有两类、三种（对科学计算）：1）公式误差——“截断误差”，数学↔计算，算法形成——主观（人为）：数学问题-数值方法的转换，用离散公式近似连续的数学函数进行计算时，一般都会发生误差，通常称之为“截断误差”；——以后讨论2）舍入误差及输出入误差——计算机，算法执行——客观（机器）：由于计算机的存储器、运算器的字长有限，在运算和存储中必然会发生最末若干位数字的舍入，形成舍入误差；在人机数据交换过程中，十进制数和二进制数的转换也会导致误差发生，这就是输入误差。

这两种误差主要是由于计算机的字长有限，采用浮点数系所致。

首先介绍浮点数系一、计算机上的运算——浮点运算面向计算机设计的算法，则先要讨论在计算机上数的表示。

科学记数法——浮点数：约定尾数中小数点之前的数全为零，小数点后第一个数不能为零。

目前，一般计算机都采用浮点数系，一个存储单元分成首数和尾数：首数l 尾数(位)其中首数存放数的指数（或“阶”）部分，尾数存放有效数字。