Berkeley COMPSCI 282 - Assignment 4 - Simplification, Integration

Unformatted text preview:

UNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 282 Prof. R. FatemanFall 2004Assignment 4: Simplification, IntegrationDue: Thursday, 1 April, 20041. Experiment with the integration programs in Maple, Mathematica, and/or Macsyma. Seeif you can come up with examples of indefinite integrals that exist in closed form in terms ofelementary functions but which they do not find. In the past, a way of doing this was to startwith expressions, and differentiate (and then rearrange or simplify). One heuristic that s ometime scauses problems is integrating a sum of terms by integrating term-by-term. What if the individualterms are not integrable, but the sum is?Can you outline some region(s) of “expression space” that characterize your discoveries?2. As illustrated in class, definite integration with a parameter, followed by a numerical substitu-tion for that parameter, can give results that differ from integration with the numerical constantin place. Try to find particularly simple examples for which this phenomenon occurs and see if youcan explain what has happened.Definite improper integrals (limits including ∞, or integrals with singularities at the endpointsor in the middle), cause problems sometimes. Consider the integrand 1/(x − a)2and variousendpoints. What should the answer be?3. In our notes we c laimed that all univariate real polynomials can be factored “numerically”into (at worst) quadratic factors over the reals, and into (at worst) linear factors over the complexnumbers. This trivializes rational function integration. Attack and/or defend this position.4. This problem concerns iteration in a power series domain. The short Macsyma program belowuses “Picard’s method” (describ e d in any elementary differential equations book) to solve a first-order ordinary differential equation by integration, but in a p ower-series domain. Write a (short)program that will solve simple second-order ODEs using the same technique. (Solving simple ODEswould include, for example, finding x(t) whered2xdt2= f (x,dxdt, t)1Assignment 4: Simplification, Integration 2for f() is a polynomial in three variables.) Picard, under some restrictions, solves the equationdxdt= f (x, t)where x(0) = a0 as a series to degree n in t. For example, you could try picard(x,x,t,1,5);picard(f,x,t,a0,n):=block([s:a0,deg:0],while deg < n do(deg:deg+1, s:ratdisrep(s),s:integrate(taylor(subst(x=s,f),t,0,deg),t)+a0),return(taylor(s,t,0,n)));To be tter understand picard, you can use debugging information from setcheck:[s,deg];and trace(integrate,taylor); etc. There is an analogy to p-adic convergence in this business,but you need not discuss it.Show that your program can solve y00+ y = 0, y(0) = 0, y0(0) = 1.Feel free to use Mathematica or Maple or Mupad instead of Macsyma. If you need help indeciphering the program, see me.5. Consider the algorithm discussed by Moses for testing for zero equivalence of an expression ina class which differs from Brown’s REX expressions in that it involves no i, only a single variablex but allows the function log(|x|). The log as well as the exponential can be nested to any depth.This algorithm (also due to D. Richardson) works by reducing the decision proce ss to one requiringthe solution to “the constant problem” of determining whether an expression consisting entirely ofconstants is zero or not.(a) What limitations are relevant on this algorithm. Give examples where these limitationscome into play. (Hint: Is this expression a constant: arctan(x) + arctan(1/x)?)(b) Describe alternative algorithms or heuristics for solving this constant problem.(c) What properties of the derivative are used by Richardson?(d) Consider the extension to Richardson’s results suggested by Moses so that the class caninclude functions specifically defined by a differential equation of the form y0= a(x)y + b(x).Describe the algorithmic details for this, and if you can, write a program for it.For example, the equation y0= (2/√π)e−x2has as its solution a function y = erf(x) that is anintegral not expressible in terms of elementary functions. Can you show that erf(x) + erf(−x)


View Full Document
Download Assignment 4 - Simplification, Integration
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Assignment 4 - Simplification, Integration and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Assignment 4 - Simplification, Integration 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?